前缀和与差分

前缀和与差分

1、一维前缀和

描述：

​ 可以在O(1)的时间算出一段区间内的所有数的和。

模板：

for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];   //预处理  计算前缀和数组

int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]);  //进行每一段的求和

注意：

​ 前缀和与差分数组下标都必须从1开始。

2、二维前缀和

描述：

​ 能够在O(1)的时间内算出一个矩阵中所有数的和。

思路：

（1）数组下标都从1开始，便于后续的处理
（2）遍历二维数组中的每一个点
构造：每一个点执行s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
（3）获取(x1, y1)与(x2, y2)之间的子矩阵的所有数的和
构造完成后的二维前缀和数组，直接输出
s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]，即可获得该子矩阵的所有数的和

代码模板：

s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];    //求二维前缀和数组

printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);  //想要的矩阵之内的所有数之和

3、一维差分

描述：

​ 用于给某个区间快速地加上或者减去某个数。

思路：

（1）构造差分数组
（1.1）将差分数组看作原本都是0，a[i]是原数组，b[i]是差分数组
（1.2）然后将原数组中的每一个数，都插入到差分数组中，
b[l] += c, //a[l]后的数都会+c
b[r + 1] -= c; //a[r + 1]后的数都会-c，【补丁】
最后达到的效果就是a[l] ~a[r]之间的每一个数都加上了c
（2）然后根据题目要求在差分数组中指定区间中的每一个数都加上一个数，即在差分数组中的该区域中插入该数
（3）将差分数组还原成原数组（前缀和数组）输出即可 b[i] += b[i - 1];

代码模板：

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);   //输入原数组
for (int i = 1; i <= n; i ++) insert(i, i, a[i]);   //将原数组变成差分数组，此时原数组为该数组的前缀和数组

//给区间[l, r]上的数都加上c
insert(l, r, c);    //将差分数组的第l个，加上c，后续在还原原数组的时候，后续到r的数，都会加上c
for (int i = 1; i <= n; i ++) b[i] += b[i - 1]; //将差分数组还原成原数组
for (int i = 1; i <= n; i ++) printf("%d ", b[i]);  //输出原数组

4、二维差分

描述：

​ 快速地将一个矩阵中所有数全部加上或者减去一个数，并求出多次操作后的结果。

思路：

（1）差分矩阵的构造：
（1.1）将差分数组看作全部都是0，将原数组中的数处理后，一个一个插入到差分数组中
（1.2）先全部上c，再将不需要加上c的地方进行补丁，即减去c
b[x1][y1] += c; //以(x1, y1)为左上角顶点的所有矩阵中的元素全部加上了c这个数
b[x2 + 1][y1] -= c; //以(x2 + 1, y1)为左上角顶点的所有矩阵中的元素全部减去了c这个数
b[x1][y2 + 1] -= c; //以(x1, y2 + 1)为左上角顶点的所有矩阵中的元素全部减去了c这个数
b[x2 + 1][y2 + 1] += c; //以(x2 + 1, y2 + 1)为左上角顶点的所有矩阵中的元素加上c这个数，前面多减了一次
（2）然后根据题目要求在差分数组中指定区间中的每一个数都加上一个数，即在差分数组中的该区域中插入该数
（3）将差分数组还原成原数组（前缀和数组）输出即可
b[i][j] += b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1];

代码模板：

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;
}

for (int i = 1; i <= n; i ++)   //读取原数组
        for (int j = 1; j <= m; j ++)
            scanf("%d", &a[i][j]);
     
for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            insert(i, j, i, j, a[i][j]);    //初始化差分数组
            
//将点(x1, y1)与点(x2, y2)形成的矩阵的所有数都加上c
insert(x1, y1, x2, y2, c);  //进行插入数字的操作 

for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            b[i][j] += b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1]; //将差分数组还原成原数组，即还原成前缀和数组
            
for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++)printf("%d ", b[i][j]);    //输出还原后的数组即可