1. 一维前缀和基本形态

class NumArray {
public:
    NumArray(vector<int>& nums) {
        sum = new int[nums.size()+1];
        sum[0]=0;
        for(int i =1;i<=nums.size();i++){
            sum[i] = sum[i-1]+nums[i-1];
        }
    }
    
    int sumRange(int left, int right) {
        return sum[right+1]-sum[left];
    }
private:
    int* sum;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

简单来说，前缀和能够解决大量连续区间求和的问题，只需要在O(n)的时间复杂度下预处理数组，然后再O(1)的复杂度下进行查询。

在上面的代码中，我们定义sum[i]的定义是该数组前i个元素的和

base-case就是前0个元素的和为0，然后开始递推计算。注意，由于right和left是指代的数组下标，所以计算区间和的下标是有不同的。由于区间是[left,right]两边都是闭的，比如说我要求[0,1]的话，那么就要包含下标为0的元素和下标为1的元素，那么这时候的话就应该是用前两个元素的和-前0个元素的和，我们看到这时候right+1

2. 二维前缀和

给定一个二维矩阵matrix，请你计算其子矩阵范围内元素的综合，该子矩阵的左上角为(row1,col1)，右下角为(row2,col2)，请你返回左上角(row1,col1)和右下角(row2,col2)所描述的子矩阵的和

注意任意子矩阵的元素可以转化成它周边几个大矩阵的元素和的运算

注意到这四个大矩阵有一个共同的特点，那就是左上角都是(0,0)原点，那么求解二维前缀和的更好思路和一维数组中的前缀和是非常类似的:可以维护一个二维的preSum数组，专门记录以原点为顶点的矩阵元素之和，就可以用常数级的时间进行二维区间和的查询

来看看二维前缀和是如何计算和维护的，上面这张图所示。i代表行,j代表列，我们用黄色部分的矩形preSum[i][j-1]加上preSum[i-1][j]这时候就会发现f[i-1][j-1]被加了两次，所以我们要减去一个preSum[i-1][j-1]，然后最终再加上martix[i][j]就是preSum[i][j]

其实这个问题也有动态规划的性质，最重要的还是定义！定义！定义

preSum[i][j]所定义的是从[0][0]到[i-1][j-1]这二维矩阵之中的所有元素的和，从中文翻译的角度来说就是求前i行前j列所构成的矩形的和。

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return ;
        }
        n = matrix.size();
        m = matrix[0].size();
        preSum = new int*[matrix.size()+1];
        for(int i = 0;i<matrix.size()+1;i++){
            preSum[i] = new int[m+1];
        }
        //定义base-case
        //当行为0的时候,计算出来面积肯定是0
        for(int i =0;i<=n;i++){
            for(int j=0;j<=m;j++){
                preSum[i][j]=0;
            }
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                preSum[i][j] = preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+matrix[i-1][j-1];
            }
        }
    }
    //计算子矩阵之和,[x1,y1,x2,y2]
    int sumRegion(int x1, int y1, int x2, int y2) {
        return preSum[x2+1][y2+1]-preSum[x1][y2+1]-preSum[x2+1][y1]+preSum[x1][y1];
    }
private:
    int** preSum;
    int n,m;
};

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

关于x1,y1,x2,y2这几个数是否加一减一，是不确定的，但是有如下的总结:

当定义的preSum[i][j]是代表前i行前j列所形成的矩形的话，那么preSum[i+1][j+1]包含住了mat[i][j]这个元素
当定义的preSum[i][j]是代表下标为i行下表为i列所形成的矩形的话，那么preSum[i][j]包含住了mat[i-1][j-1]，只需要抓住这两个点就能够明白什么时候要加+1，什么时候不用了。

3.差分数组法

与前缀和相对的，有一种算法是差分数组，下面来介绍一下两者的联系以及区别，首先回顾一下最简单的一维下的前缀和

private int[] preSum;
void preDeal(int[] nums){//前缀和预处理
    preSum = new int[nums.length];
    //定义前缀和数组的定义:前i个元素的和
    //base-case
    //前0个元素的和是0
    preSum[0] = 0;
    for(int i = 1;i<nums.length;i++){
        preSum[i] = preSum[i-1] + nums[i-1];
    }
}

int getSum(int i,int j){
    //这个如何来控制?
    //我们预想得到[i,j]之间的值
    //那么我们就想要得到的是Sum[j]-Sum[i-1]
    //对应的定义来说就是
    return preSum[j+1] - preSum[i];
}

前缀和的适用场景是用于频繁地对区间进行求和的过程，差分数组的主要适用场景是频繁对原始数组的某个区间进行增减

一般如下进行代码定义

int[] diff;
//构造差分数组
//差分数组的定义:第i个元素与第i-1个元素的差
void preDeal(int[] nums){
    diff = new int[nums.length];
    //base-case
    diff[0] = nums[0];
    for(int i = 1;i<nums.length;i++){
        diff[i] = nums[i] - nums[i-1];
    }
}

void modify(int i,int j,int val){
    diff[i] += val;
    for(int k  = j+1;k<diff.length;k++){
        diff[k] -= val;
    }
}

int[] res;
res[0] = diff[0];
void getRes(){//还原
    for(int i = 1;i<diff.length;i++){
        //因为diff[i]是nums[i]和nums[i-1]的差
        res[i] = res[i-1] + diff[i];
    }
}