前缀和技巧

前缀和技巧适用于的场景是原始数组不会被修改的情况下，频繁地查询某个区间地累加和。

大致框架如下所示：

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

LeetCode例题 303 304 560

差分数组

差分数组主要适用于对原数组地某个区间的元素进行频繁的增减。

大致框架如下：

class Difference{
private:
    vector<int> diff;
    
public:
    Difference(vector<int>& nums) {
        assert(nums.size() > 0);
        int len = nums.size();
        diff.resize(len);
        diff[0] = nums[0];
        for (int i = 1; i < len; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }
    
    void increment(int i, int j, int val) {
         diff[i] += val;
        if (j + 1 <diff.size()) {
            diff[j + 1] -= val;
        }
    }
    
    vector<int> getResult() {
        vector<int> result;
        result[0] = diff[0];
        for (int i = 1; i < diff.size(); i++) {
            result[i] = diff[i] + diff[i - 1];
        }
        return result;
    }
}

LeetCode例题有1109和1094