前缀和以及差分的解题步骤与技巧

前缀和以及差分问题：

导论：

该博客记录前缀和问题以及差分的解题步骤与相应公式;

理解其中变化，有不完善的地方慢慢补全；

如果有错误欢迎指出！

前缀和：

首先需要知道前缀和的概念：即数组该位置之前的元素之和。

还有一个重要的点，在进行前缀和的运算时，下标从1开始，设数组a[0]=0;

比如a[5] = {0,1,2,3,4};

求a[1]的前缀和：a[1];

求a[2]的前缀和：a[1]+a[2];

…

为什么下标要从1 开始：为了方便后面的计算，避免下标转换，设为零，不影响结果

前缀和的作用： 快速求出元素组中某段区间的和

一维数组的前缀和问题:

求数组a中（l，r）区间的和 —>用到前缀和

二维数组的前缀和问题:

方法与一维数组大体相同：需要中间数组s[i][j]

差分问题：

首先明白差分的概念：差分其实就是前缀和的逆运算

差分的作用：如果对某个区间需要每个元素加上C则需要使用差分来减少时间复杂度

差分的重点是：构造临时数组b[]

b[1] = a[1]
b[2] = a[2] - a[1]
b[3 ]= a[3] - a[2]
...
b[n] = a[n] - a[n-1]

两个数组：S[],b[]，S[]称为b[]的前缀和，b[]称为S[]的差分

差分的下标也是从1开始

前缀和差分是2个互逆的运算，假设最开始的数组是a[i], 则前缀和数组sum[i]表示从a[1]+…+a[i];而差分数组b[1]+…+b[i]则表示a[i],即a[i]是差分数组b[i]的前缀和;

一维数组的差分问题：

二维数组的差分问题：

记住：a[][]数组是b[][]数组的前缀和数组，那么b[][]是a[][]的差分数组

二维差分的核心也是构造差分数组b[][],使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和；

怎么让子矩阵中的每个元素加上c;

先定义一个函数：

public static void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1] += c;
    b[x2+1][y1] -=c;
    b[x1][y2+1] -=c;
    b[x2+1][y2+1] +=c;
}

结束：

感谢各位能看到最后