算法总结

前缀和

概念

首先，前缀和在一维的层面上可以理解为数列前n项和，对于二维矩阵，则为以a[i][j]到a[1][1]之间的所有元素的和。

作用

快速求出数组某段区间（某个子矩阵）之间的和。

算法

一维

/*创建一个源数组，再创建一个前缀和数组，
需要注意的是：
1.数组的开头都是以1开始，其作用一是符合人的习惯，二是便于前缀和a[0]=a[-1]+x这种情况发生。
2.公式：求l～r之间的值：sum=p[r]-p[l-1];
*/
int q[n],p[n];

void add()//计算q的前缀和，并将其存入p数组，p[i]的值即代表q数组中前i项和的值
{
    for(int i=1;i<=n;i++) p[i]=q[i]+p[i-1];
}

int func(int l,int r)//计算q数组l～r之间元素的值，
{
   int sum=p[r]-p[l-1];

   return sum;
}

二维

int q[m][n],int p[m][n];

void add()//计算前缀和
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+q[i][j];//公式
/*其实对于这个公式可以这么理解：我们看到的q[i][j]数组，实际上是前ixj个p中元素的和，我们计算p[i][j]时，分别减去了另外两个前缀和，但是减去他们减多了，需要加上一个前缀和（一会贴一张图上来就好理解了）*/
}

int func(int x1,int y1,int x2,int y2)
//计算子矩阵从q[x1][y1]到q[x2][y2]中元素的和
{
int sum=p[x2][y2]-p[x1-1][y2]-p[x2][y1-1]+p[x1-1][y1-1];//公式有没有一点感觉，这个公式是与上面那个公式相反的？    

return sum;
}

差分

概念

可以理解为前缀和的逆运算，即已知前缀和，通过差分数组对前缀和进行操作

作用

当我们需要对一个数组中某一区间整体加或者减时，如果不用差分，直接暴力的时间复杂度是O(n),而通过差分，时间复杂度为O（1）

基本流程（贴一张图吧

算法

一维

int q[n],p[n];

void insert(int l，int r,int c)//差分数组的操作
{
        p[i]+=c;
        p[i+1]-=c;//公式，还需要理解怎么推出来的（贴图
}

for(int i=1;i<=n;i++) insert(i,i,q[i]);//构建差分数组

insert(int l;int r;int c)//对数组中从l-r之间的所有元素都加上c

void add()
{
    for(int i=1;i<=n;i++) p[i]=p[i-1]+p[i];//同上，求前缀和，不过是直接在p数组中直接更新了值
}

二维

int q[m][n],p[m][n];
void insert(int x1,int y1,int x2,int y2,int c)
{
    q[x1][y1]+=c;
    q[x1][y2+1]-=c;
    q[x2+1][y1]-=c;
    q[x2+1][y2+1]+=c;
}

for(int i=1;i<=m;i++)//构建差分数组
    for(int j=1;j<=n;j++)
        insert(i,j,i,j,q[i][j]);

insert(x1,y1,x2,y2,c);//对差分矩阵进行操作

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        q[i][j]=q[i-1][j]+q[i][j-1]-q[i-1][j-1]+q[i][j];//对差分矩阵求前缀和

总结起来：

差分和前缀和就是一个相互依存的关系，其中差分里面公式的推导过程需要记牢（抽点时间搞懂怎么推的）

碎碎念时间：

哎呀哎呀 本来我是有超级多的牢骚想要发泄一下的，但是现在是凌晨1:04，我也没想到自己的第一篇博客？会花这么多时间，一边学习使用markdown的同时，还要学习探索macos的快捷键操作，确实挺慢的，中途跑去学快捷键思路断了，下次别搞了啊小兄弟，先盯紧目标，哪怕稍微绕一代呢弯路，你他喵的去找捷径找着找着人没了！！！
最后 apple真他喵牛逼，在AcWing上敲代码用pad真的爽呀，去了解一下配个鼠标是什么感觉呀，那不直接起飞？？？
最最后，预祝算法学习的过程中你能坚持下去呀，努力的过程也是强大的过程，每天没有技术总结的话，在这里来写一点日记也挺好的哦，也许也没人看到，不必隐藏，talk to yourself!
哦哦哦 还有！！！ 多保存啊，每次完事了用safari截一个长图，以防万一啊，万一，有一天网站崩了，你的必生所学也寄了。