前缀和与差分数组

今天在看东哥的算法笔记时学习了两个以空间换时间的算法技巧，前缀和和差分数组。但是在刷题的时候不以为然，多层for循环走天下，直到测例超时才幡然醒悟，悔之晚矣呀！
但是还是不得不吐槽一下，leetcode的某些测试用例……

前缀和

前缀和适用于需要快速，频繁的计算一个索引区间内的元素之和的场景。
对于一个长度为n的一维数组nums，维持一个长度为n+1的前缀和数组presum，其中，

$$presum[i] = \sum_{a=0}^{i-1} nums[a]$$

这样，我们在计算nums数组的一个索引区间内的元素之和时，只需要使用presum中的相应元素进行一次加减法运算即可。

$$\begin{align*} sum(nums[i], nums[j]) &= presum[j+1] - presum[i] = \sum_{a=0}^{j} nums[a] - \sum_{a=0}^{i-1} nums[a] \\ &=\sum_{a=i}^{j} nums[a] \end{align*}$$

这种做法在仅需进行少量计算时，不如直接用for循环进行遍历求和，但当需要进行多次快速检索时，前缀和数组的优越性就体现出来了。

实例

• 题解：

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

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

同样的，前缀和的方法也适用于二维数组。

差分数组

类似与前缀和技巧，差分数组的思想是额外的维持一个长度为n的差分数组differ。

$$differ[i] = nums[i] - nums[i-1]$$

差分数组中的元素表示了原数组中相应位置上的元素与其前一个元素之间的差。差分数组的适用于我们需要频繁的对nums进行批量操作时。比如，场景要求我们对区间nums[2…6]全部加1，做一次这样的操作，只需要for循环遍历即可，但是，若是操作的太多，效率将极为低下。而若是使用差分数组，每次对区间i，j进行操作，只需要在差分数组的对应位置进行两次加减法操作即可，前者的时间复杂度为$O(n)$，而后者的时间复杂度仅为$O(1)$。

实例

• 题解：

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        // 超时
        // vector<int> ans(n, 0);
        // for(auto p : bookings){
        //     for(int i = p[0]; i <= p[1]; i++){
        //         ans[i-1] += p[2];
        //     }
        // }
        // return ans;
        
        // 构建差分数组
        vector<int> differ(n + 1, 0);
        for(auto p : bookings){
            differ[p[0]] += p[2];
            if(p[1]+1 < differ.size())
                differ[p[1]+1] -= p[2];
        }
        // 从差分数组恢复出原数组
        vector<int> ans(n, 0);
        ans[0] = differ[1];
        for(int i = 2; i < differ.size(); i++){
            ans[i-1] = ans[i-2] + differ[i]; 
        }
        return ans;
    }
};