首页 书籍 深入浅出程序设计竞赛(进阶篇)

差分是一种用于处理数组或序列 “区间增减” 操作的技术，它可以让我们在 O (1) 的时间复杂度内完成对一个区间内所有元素的增加或减少操作，而直接更新整个区间的元素则可能需要 O (n) 的时间复杂度。差分技术常与前缀和技术配合使用，前缀和用于快速查询区间和，而差分用于高效地修改区间值。

# 差分数组

对于一个给定的数组 arr ，其差分数组 diff 定义为每个位置上的元素与前一个位置上元素的差值，即 diff[i] = arr[i] - arr[i-1] 。为了方便处理，我们通常假设 diff[0] = arr[0] 。

差分数组的主要作用是快速进行区间增减操作。如果我们想要将 arr 数组中从第 l 个元素到第 r 个元素（包括 l 和 r ）增加一个值 val ，我们只需要将 diff[l] 增加 val ，并将 diff[r+1] 减少 val （如果 r+1 在数组范围内）。这样做的原因是，当我们基于差分数组重新计算原数组时，从 l 到 r 的所有元素都会增加 val ，而 r+1 之后的元素不受影响。

# 示例代码

下面是构建差分数组和基于差分数组进行区间修改的示例代码：

#include <iostream>
#include <vector>
using namespace std;
class Difference {
private:
    vector<int> diff; // 差分数组
public:
    // 构造函数，计算差分数组
    Difference(vector<int>& nums) {
        diff.resize(nums.size());
        diff[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }
    // 对区间 [l, r] 增加 val（包括 l 和 r）
    void increment(int l, int r, int val) {
        diff[l] += val;
        if (r + 1 < diff.size()) {
            diff[r + 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;
    }
};
int main() {
    vector<int> nums = {8, 2, 6, 3, 1};
    Difference diff(nums);
    
    // 假设我们想要将区间 [1, 3] 内的所有元素增加 4
    diff.increment(1, 3, 4);
    vector<int> result = diff.result();
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}
在这个例子中，我们首先根据原始数组 nums  构造了差分数组 diff ，然后通过调用 increment  方法对指定区间进行修改，最后通过 result  方法基于差分数组恢复并输出修改后的原数组。


# 应用场景


差分技术非常适合处理数组的区间修改问题，尤其是当我们需要频繁对数组的某些区间进行增加或减少操作，而最终只关心数组的最终状态时。这种技术广泛应用于数据结构、算法竞赛和某些特定领域的问题解决方案中。


      

          
          
      

  


   


    

  
    
      
    
    更新于