https://mp.weixin.qq.com/s/123QujqVn3--gyeZRhxR-A

前缀和数组

前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。对于一维数组的实现如下：

class NumArray {
private:
	// 前缀和数组
    vector<int> preSum;
public:
	// 输入一个数组，构造前缀和数组
    NumArray(vector<int> nums)
    {
    	int n = nums.size();
    	preSum.resize(n+1); // preSum[i]表示nums数组前i个元素之和
        preSum[0] = 0; // 便于计算累加和
        // 计算 nums 的累加和
        for(int i = 1; i <= n; i++)
        {
        	preSum[i] = preSum[i-1] + nums[i-1];
        }
    }
    // 查询闭区间[left,right] 的累加和
    // left下标对应着nums数组中的第left+1个位置
    // right下标对应着nums数组中的第right+1个位置
    int sumRange(int left, int right)
    {
    	return preSum[right+1] - preSum[left];
    }
};

二维矩阵中的前缀和

class NumMatrix {
private:
	vector<vector<int>> preSum; // preSum[i][j]表示前i行前j列的元素和
public:
	NumMatrix(vector<vector<int>> matrix)
    {
    	int m = matrix.size(), n = matrix[0].size();
        preSum.resize(m+1);
        for(int i=0; i <= m; i++)
        	preSum[i].resize(n+1);
        for(int i = 1; i <= m; i++)
        {
        	for(int j = 1; j <= n; j++)
            {
            	preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i-1][j-1] - preSum[i-1][j-1];
            }
        }
    }
    // 计算子矩阵[x1,y1,x2,y2]的元素和
    int sumRange(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];
    }
};

差分数组

比如说，给定一个数组nums，然后又要求给区间nums[2,...,6]全部加1，再给nums[3,...,9]全部减1，再给nums[0,...,4]全部加2，再给...，经过这一系列操作后问你，最后nums数组的值是多少？可以有以下两种解法：

常规解法对于每一个给区间做加减法的操作，使用一个for循环来实现，时间复杂度是O(N)，如果对nums的修改非常频繁，会使得效率低下。 2.差分数组类似于前缀和技巧构造的preSum数组，可以先对nums数组构造一个diff差分数组，diff[i]就是nums[i]和nums[i-1]的差值。

vector<int> diff(nums.size());
// 构造差分数组
diff[0] = nums[0];
for(int i = 1; i < nums.size(); i++)
{
	diff[i] = nums[i] - nums[i-1];
}

通过这个diff差分数组是可以反推出原始数组nums的，代码如下：

vector<int> nums(diff.size());
// 根据差分数组构造原始数组
nums[0] = diff[0];
for(int i = 1; i < diff.size(); i++)
{
	nums[i] = diff[i] + nums[i-1];
}

这样构造差分数组diff，就可以快速进行区间增减的操作。假如你想对区间nums[i,...,j]的原始全部加3，那么只需让diff[i] += 3,diff[j+1] -= 3即可。原理很简单，回想diff数组反推nums数组的过程，diff[i] += 3意味着给nums[i,...]所有的原始都加3，然后diff[j+1] -= 3又意味着对于nums[j+1,...]所有元素再减3，这样综合起来就是对nums[i,...,j]区间的元素加3了。对于差分数组，我们可以抽象成一个类，包含increment方法和result方法：

// 差分数组工具类
class Difference {
private:
	// 差分数组
    vector<int> diff;
public:
	// 输入一个初始数组，区间操作将在这个数组上进行
    Difference(vector<int> nums)
    {
    	int n = nums.size();
    	diff.resize(n);
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for(int i = 1; i < n; i++)
        {
        	diff[i] = nums[i] - nums[i - 1];
        }
    }
    // 给闭区间[i,j]增加val（正负均可）
    void increment(int i, int j, int val)
    {
    	diff[i] += val;
        if(j + 1 < diff.size())
        {
        	diff[j + 1] -= val;
        }
    }
    // 返回结果数组 也就是根据差分数组构建结果数组
    vector<int> result()
    {
    	vector<int> res(diff.size());
        res[0] = diff[0];
        for(int i = 1; i < diff.size(); i++)
        {
        	res[i] = res[i-1] + diff[i];
        }
        return res;
    }
};

总结

前缀和数组主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和；而差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

前缀和数组与差分数组

前缀和数组

差分数组

总结