一维前缀和：

1. 如何算：s[i] = a[1] + a[2] + …… + a[i] // 下标必须从1开始，s[0] = 0

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

2. 有什么用

计算数组[l, r]之间的数据和：s[r] - s[l - 1]

二维前缀和

1. 如何算

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

2. 求子矩阵的和：(x1, y1) 到 (x2, y2)

s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]

一维差分

1. 定义

由前缀和数组a[]计算出原数组b[]

2. 作用

在O(1)的时间复杂度内实现对前缀和数组a[]的[l, r]区间内所有元素 + C的操作
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

二维差分

(图片中S改成b数组)

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