前缀和

一维

一维数组中，计算出所有前 n 个数的和，存储在一个单独的数组里，便于后续计算

板子

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

s[i] 计算的就是前 i 个数的和
当我们需要计算第 l 个数到第 r 个数的和时，只需要用 s[r] - s[l - 1] 即可

二维

二维数组中，计算出长为 0 - l， 宽为 0 - r 的矩阵和
这个值等于长为 0 - (l - 1) 宽为 0 - r 的矩阵加上 长为 0 - l 宽为 0 - (r - 1) 的矩阵减去 长为 0 - (l - 1) 宽为 0 - (r - 1)的矩阵 最后加上该位置的值

板子

for (int i = 1; i <= n; i ++ )
{
    for (int j = 1; j <= m; j ++ )
    {
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    }
}

当我们需要计算左上角坐标为 (x1, y1)， 右下角坐标为 (x2, y2) 的矩阵时，只需要用 s[x2][y2] - s[x1 - 1][y1] - s[x1][y1 - 1] + s[x1 - 1][y1 - 1] 即可

差分

差分与前缀和是逆运算，数组 a 是数组 b 的前缀和，数组 b 就是数组 a 的差分
即
a[i] = b[0] + b[1] + … + b[i]
b[i] = a[i] - a[i - 1]

一维

在一维数组中，将从 l 到 r 的每一个数都加上给定值 c
因为在给定区间内的每一个数都加了 c ，所以它们之间的差值不变，只有第 l - 1 与第 i 个数、第 r 与第 r + 1 个数的差值发生了改变，因此修改差分数组时只需要修改两个值，极大提高计算速度
适用于需要多次修改数组的情况

板子

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

for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]); // 差分数组的建立
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c); // 差分数组的修改
for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1]; // 将差分数组恢复成原数组

二维

二维数组中，将长为 0 - l， 宽为 0 - r 的矩阵中每一个元素都加上一个给定值 c
对于差分矩阵，需要进行如下操作：

  • b[x1][y1] += c
  • b[x2 + 1][y2 + 1] += c
  • b[x2 + 1][y1] -= c
  • b[x1][y2 + 1] -= c

板子

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

for (int i = 1; i <= n; i ++ )
	for (int j = 1; j <= m; j ++ )
        cin >> 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]); // 构造差分数组
int x1, y1, x2, y2, c;
cin >> 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 - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; // 恢复原数组