前缀和、差分

前缀和（求解指定区间和）

算法原理

下列数组下标都是从1开始
原数组nums         0 1 3 5 7 9
前缀和sum          0 1 4 9 16 25                
sum[3]-sum[1] 就是num[2]+nums[3]

// getSum(1,3) 区间和就是 nums[1]+num[2]+num[3] 范围
int getSum(int l, int r, vector<int>& sum){
    return sum[r] - sum[l-1];
}

算法模板，推荐算法2

// 算法1
// nums下标从0开始
vector<int> nums = {1,2,3};
// 0, 1, 3, 6
vector<int> sum{0};
for(int a: nums){
    sum.push_back(sum.back()+a);
}
// [l,r] 区间和， 注意 l r 下标是从1开始，nums下标从0开始
// 计算[1,3]区间和就是 nums[0]+num[1]+num[2] 范围
int getSum(int l, int r, vector<int>& sum){
    return sum[r] - sum[l-1];
}


// 算法2 
// nums下标从1开始,0位置浪费
vector<int> nums = {0, 1, 2, 3};
                 // 0, 1, 3, 6
vector<int> sum(nums.size());
for (int i = 1; i < nums.size(); i++) {
    sum[i] = nums[i] + sum[i-1];
}

// 计算[1,3]区间和就是 nums[1]+num[2]+num[3] 范围
int getSum(int l, int r, vector<int>& sum){
    return sum[r] - sum[l-1];
}


// nums下标从0开始
vector<int> nums = {1, 2, 3};
// 0, 1, 3, 6
vector<int> sum(nums.size()+1);
for (int i = 1; i <= nums.size(); i++) {
    sum[i] = nums[i-1] + sum[i-1];
}

// [l,r] 区间和， 注意 l r 下标是从1开始，nums下标从0开始
// 计算[1,3]区间和就是 nums[0]+num[1]+num[2] 范围
int getSum(int l, int r, vector<int>& sum){
    return sum[r] - sum[l-1];
}

差分（求解区间加减问题）

差分原理

下列数组下标都是从1开始，区间[1,n]
原数组nums         0 1 3 5 7 9
差分数组dif         0 1 2 2 2 2
差分数组前缀和sum    0 1 3 5 7 9                
刚好还原数组

如果要把[1,3]区间数组都加1，只需要dif[1]+1, dif[4]-1
差分数组dif         0 2 2 2 1 2
差分数组前缀和sum    0 2 4 6 7 9 

// [l,r] 区间加上val 
// 注意 l r 下标是从1开始，nums下标从1开始
// add(1,3,10) 就是 nums[1]到nums[3] 全部加10
int add(int l, int r, int val, vector<int> &dif) {
    dif[l] += val;
    dif[r + 1] -= val;
}

差分代码

// nums下标从1开始,0位置浪费,但是nums[0]必须是0
vector<int> nums = {0, 1, 3, 5, 7, 9};
                 // 1, 2, 2, 2, 2, 2 
vector<int> dif(nums.size());
for (int i = 1; i < nums.size(); i++) {
    dif[i] = nums[i] - nums[i-1];
}

// [l,r] 区间加上val 
// 注意 l r 下标是从1开始，nums下标从1开始
// add(1,3,10) 就是 nums[1]到nums[3] 全部加10
int add(int l, int r, int val, vector<int> &dif) {
    dif[l] += val;
    dif[r + 1] -= val;
}
// 得到进行多次add操作后的数据值
int recover(vector<int>& dif, vector<int>& nums){
    // nums[0]永远是0,nums下标从1开始
    for(int i = 1; i < nums.size(); i++) {
        nums[i] = nums[i-1] + dif[i];
    }
}