$\Huge\color{orchid}{点击此处获取更多干货}$

多元前缀和

线性序列前缀和能和单个随机变量$X$的概率分布函数相对应，那多维表“前缀和”也有多维随机变量$(X,Y,Z,…)$的概率分布函数与之对应，比如二维离散型随机变量$(X,Y)$的概率分布函数定义为：
$$F_{X,Y}(x,y)=P( X\le x,Y\le y ) =\sum_{i=x_0}^{x} \sum_{j=y_0}^{y} P ( X=i,Y=j ) $$

同样也有类似定义$P(x_1<X\le x_2,y_1<Y\le y_2)=F(x_2,y_2)-F(x_2,y_1)-F(x_1,y_2)+F(x_1,y_1)$

结合上图可知，$(X,Y)$处于S区域内的概率等于大区域概率减去三个小区域的概率a,b,c，但是从分布函数推导的时候，区域b的值被减了两次，需要还回去一次。因此对于矩阵中某区域的元素和，也可以用上述类似的方法，用一个前缀和矩阵存放$(0,0)$为左上角，当前位置为右下角的矩阵区域元素和。不过构造前缀和矩阵的时候，每一个位置上元素的值不再由单个位置决定，而是由左方、上方、左上方三个位置决定。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

int** preSum;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q, x;//x是当前值
    cin >> n >> m >> q;
    //同样，把0行和0列都置为0
    //C++20可以new的时候直接用()赋值
    preSum = new int* [n + 1];
    for (int i = 0; i <= n; i++) {
        preSum[i] = new int[m + 1];
        fill(preSum[i], preSum[i] + m + 1, 0);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> x;
            //当前位置      上方位置            左方位置            左上位置
            preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + x;
        }
    }
    int x1, x2, y1, y2;
    while (q--) {
        cin >> x1 >> y1 >> x2 >> y2;
        //按照图上类似的方法求区域和
        cout << preSum[x2][y2] - preSum[x1 - 1][y2] - preSum[x2][y1 - 1] + preSum[x1 - 1][y1 - 1] << endl;
    }
    for (int i = 0; i <= n; i++) {
        delete[] preSum[i];
    }
    delete[] preSum;
    return 0;
}