前缀和数组与差分数组

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;
    }
};