差分前缀和
前缀和
预处理后可以用O(1)的时间复杂度求一个区间的值 能显著降低查询时间复杂度
一维
(从原数组)构建
a[0] = 0;
for(int i = 1;i <= n; i++) {
a[i] += a[i-1];
}
查询[l,r]区间的和
a[r] - a[l-1]
``
二维
求一个矩形区域的所有值的和 (从原数组)构建
for(int i = 0; i <= m; i++) sum[0][i] = 0;
for(int i = 0; i <= n; i++) sum[i][0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; i <= m; j++) {
sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
查询(x1,y1)和(x2,y2)包裹的矩形区域内的和
int query(int x1 ,int y1 ,int x2, int y2) {
return sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
}
差分
一维
不支持边操作边查询 数组$a$在一个区间$[l,r]$上每个位置都增加相同的值$x$ 如果$a[i] = x$; 含义是，无限远的数轴上从i位置(包括)开始，每个位置的值变化$x$ 可用差分数组标记
a[l] += x;
a[r+1] -= x;
求前缀和即可得到每一位的值
等差序列差分
s d-s 0 0 ... 0 -e-d e
s d d d ... d -e 0
s s+d s+2d s+3d ... e 0 0
进行标记
void op(int l, int r, int s, int e,int d) {
ans[l] += s;
ans[l + 1] += d - s;
ans[r + 1] += -e - d;
ans[r + 2] += e;
}
求两次前缀和即可
二维差分
$sum$数组在(x1,y1)和(x2,y2)包裹的矩形区域内每个sum[i][j]的值增加v。
如果sum[x][y] = v，那么大于等于$i >= x,j >= y$的位置的点所有点sum[i][j]的值都增加v
void add(int x1, int y1, int x2, int y2, int v) {
sum[x1][y1] += v;
sum[x2 + 1][y2 + 1] += v;
sum[x2 + 1][y1] -= v;
sum[x1][y2 + 1] -= v;
}
之后再求一遍二维前缀和就可以得到每个点的值