https://blog.csdn.net/k_r_forever/article/details/81775899
已知一个数组，对其进行以下操作：
区间修改。
在所有区间修改都结束后，区间查询。
设数组大小为n，询问次数为m，则线段树或树状数组的时间复杂度为，前缀和+差分的时间复杂度是
。
前缀和：。
差分：。
先设所有差分为0，区间修改只修改l和r+1的差分，修改完成后先计算差分的累积和，再由
算出
的前缀和，查询的时候用
。（这种算法也可以单点修改和单点查询）
#include<iostream>
using namespace std;
const int maxn = 500010;
int n, m;
int s[maxn], d[maxn];
int temp ,x, y, k, add;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> k;
d[x] += k;
d[y + 1] -= k;
}
for (int i = 1; i <= n; i++) {
add += d[i];
s[i] += s[i - 1] + add;
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
cout << s[y] - s[x - 1] << endl;
}
return 0;
}
二维前缀和：
已知一个二维数组（矩阵），给出
个询问：
，求以
为左上角，
为右下角的子矩阵的元素和（包含左上角和右下角的元素）。
这题也可以用线段树做，不过要用二维线段树，很麻烦。
想到容斥原理，设从到
的子矩阵元素和为
，有：
。
查询的时候，又有：
。
#include<iostream>
using namespace std;
int m, n;
int s[1001][1001];
int sx, sy, ex, ey;
int main() {
cin >> m >> n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> s[i][j];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
while (1) {
cin >> sx >> sy >> ex >> ey;
cout << s[ex][ey] - s[sx - 1][ey] - s[ex][sy - 1] + s[sx - 1][sy - 1] << endl;
}
return 0;
}
二维前缀和也可以用差分，要修改四个位置：
d[x1][y1]+=p;d[x2+1][y2+1]+=p;
d[x2+1][y1]-=p;d[x1][y2+1]-=p;
