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;