基础模板(Basic)
差分和前缀和

一维前缀和

求区间 $[l, r]$ 所有元素的和。

S[i] = a[1] + a[2] + ... a[i];
a[l] + ... + a[r] = S[r] - S[l - 1];

二维前缀和

设 $S[i][j]$ 为第 $i$ 行 $j$ 列格子左上部分所有元素的和;

以 $(x1, y1)$ 为左上角,$(x2, y2)$ 为右下角的子矩阵的和为:

S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1];

一维差分

给区间 $[l, r]$ 中的每个数加上 $c$

B[l] += c, B[r + 1] -= c;

二维差分

给以 $(x1, y1)$ 为左上角,$(x2, y2)$ 为右下角的子矩阵中的所有元素加上 $c$:

S[x1][y1] += c, S[x2 + 1][y1] -= c, S[x1][y2 + 1] -= c,
S[x2 + 1][y2 + 1] += c;