二维前缀和

问题描述：
给定一个矩阵，每次询问子矩阵的和（共有Q次询问）
一个二维矩阵(数组)n*m
求S[（r1,c1）~(r2,c2)]的和

问题解决：（看作二维数组）
 S[(r1,c1)~(r2,c2)]=
 S[(1,1)~(r2,c2)]
-S[(1,1)~(r1-1,c2)]
-S[(1,1)~(r2,c1-1)]
+S[(1,1)~(r1-1,c1-1)] 

S[1][1]=a[1][1]
S[1][2]=a[1][1]+a[1][2]=S[1][1]+a[1][2]
S[1][3]=a[1][1]+a[1][2]+a[1][3]=S[1][2]+a[1][3]
S[1][i]=S[1][i-1]+a[1][i]
S[2][i]=S[2][i-1]+a[2][i]
...
...
...
n个一维度前缀和
再按列来看
S[1]
S[2]
.
.
.
S[n]

1. 二维区域和检索 - 矩阵不可变
   例题

class NumMatrix {
public:
    vector<vector<int>> s;
    NumMatrix(vector<vector<int>>& mt) {
        int n=mt.size();//行数
        if(!n) return;
        int m=mt.front().size();//列数
        if(!m) return;
        //n x m的矩阵
        //以（1，1）作为左上角起始下标
        s.assign(n+1,vector<int>(m+1,0));//申请空间
        for(int i=1;i<=n;i++)//先按行
        {
            for(int j=1;j<=m;j++)
            {
                //对于每一行都是一个一维前缀和数组
                //处理第i行
                s[i][j]=s[i][j-1]+mt[i-1][j-1];//注意下标
            }
        }
        for(int j=1;j<=m;j++)//再按列
        {
            for(int i=1;i<=n;i++)
            {
                s[i][j]+=s[i-1][j];//在原本的基础上滚动加 不断累积上面一行
            }
        }
        //预处理完毕


    }

    int sumRegion(int row1, int col1, int row2, int col2) {

        row1++;//题目中从（0，0）开始 转化为（1，1）开始
        col1++;
        row2++;
        col2++;
        return s[row2][col2]-s[row2][col1-1]-s[row1-1][col2]+s[row1-1][col1-1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */