#差分数组

快速回顾一个前缀和（Prefix Sum）章节，前缀和是为了解决 “频繁查询一个固定数组某个区间的和” 这一问题的，通过预先得到前缀和数组，让每次查询区间和的操作从之前通过循环去累加求和，变为一个简单的减法操作，从而降低算法复杂度，提升了程序的运行效率。

差分类似，只是最初的所求的问题稍有一点变化，从频繁求区间和变为频繁对区间的元素进行操作。

#问题背景

假设我们有这样一个需求，给定一组共 n 个整数，需要查询从第 l 个元素到第 m 个元素范围内所有元素的和。如何去求？

例如，对于下面的输入数据

第一行的 7 3 5 10 ，7 代表 n，也就是第二行给出 7 个数据，3 5 10 表示要对第 3 个元素到第 5 元素之间（包括第 3 和第 5 个元素）的所有元素增加10 。

增加后的数组变为

#朴素解法

问题很清楚，求解也很简单，通过一个循环对区间范围内的所有元素进行一个增减操作即可。

参考代码如下：

#include <bits/stdc++.h>
using namespace std;

int n, l, m, x;
int q[110];
int main() {
  cin >> n >> l >> m >> x;
  
  for (int i = 1; i <= n; i++) cin >> q[i];
  
  for (int i = l; i <= m; i++) {
    q[i] = q[i] + x;
  }
  
  for (int i = 1; i <= n; i++) {
    cout << q[i] << " ";
  }
  return 0;
}

#问题拓展

如果我们有 k 次这样操作呢？

例如，有下面的输入数据

第一行的 3，代表有 3 次这样的区间操作，分别是：

1. 2 4 10，对 [2, 4] 区间的 3 个元素增加 10，结果为 [1 12 13 14 5 6 7]

• 1 5 4，对 [1, 5] 区间的 5 个元素增加 4，结果为 [5 16 17 18 9 6 7]
• 3 5 -1，对 [3, 5] 区间的 3 个元素减去 1，结果为 [5 16 16 17 8 6 7]

输出原数组经过增减操作后的最终结果

#拓展问题朴素解法

用同样的朴素解法，只是多了一层循环，对每一组区间数据进行操作，参考代码如下：

#include <bits/stdc++.h>
using namespace std;

int n, k, l, m, x;
int q[110], c[110];
int main() {
  cin >> n >> k;

  for (int i = 1; i <= n; i++) cin >> q[i];

  while (k--) {
    cin >> l >> m >> x;
    for (int i = l; i <= m; i++) {
      q[i] += x;
    }
  }
  
  for (int i = 1; i <= n; i++) {
    cout << q[i] << " ";
  }
  
  return 0;
}

朴素解法的时间复杂度为 $O(n \times k)$。

#差分求解

同样的，差分求解的目的是降低算法复杂度，提升算法效率。

#什么是差分

差分，可以理解为“相邻元素之间的差值”。

假设原数组 A = [1 2 3 4 5]，我们创建一个新的数组 diff，diff[i] 存储的是原数组 A 中第 i 个元素与第 i - 1 个元素的差值。

diff[1] = A[1] = 1
diff[2] = A[2] - A[1] = 2 - 1 = 1
diff[3] = A[3] - A[2] = 3 - 2 = 1
diff[4] = A[4] - A[3] = 4 - 3 = 1
diff[5] = A[5] - A[4] = 5 - 4 = 1

因此差分数组 diff 是：[1 1 1 1 1]。

一个有意思的发现：差分数组的前缀和数组刚好就是原数组！ ，我们来计算一下前缀和数组 prefix_sum。

prefix_sum[1]=A[1] = 1
prefix_sum[2]=A[1]+A[2] = 1+1 = 2
prefix_sum[3]=A[1]+A[2]+A[3] = 1+1+1 = 3
prefix_sum[4]=A[1]+A[2]+A[3]+A[4] = 1+1+1+1 = 4
prefix_sum[5]=A[1]+A[2]+A[3]+A[4]+A[5] = 1+1+1+1+1 = 5

可以看到，差分数组的前缀和恰好还原了原数组 A，这个性质非常关键！

实际上，关于差分数组与前缀和数组的关系有点像“互逆”，它们之间可以相互转换。

1. 差分数组的前缀和是原数组
2. 前缀和数组的差分是原数组

#利用差分求解

知道了什么是差分，也知道了差分与原数组，差分与前缀和之间的关系，那如何利用差分来快速对区间修改进行处理呢？

如果对于下面一组数据

将原数据 [3 5] 这个区间范围内的所有数字增加 3，结果变为

可以发现，如果从差分的角度来看：

• 原数据的差分数组为 [1 1 1 1 1 1 1]
• 新数据的差分数组为 [1 1 4 1 1 -2 1]

可以发现，恰好是 [3 5] 这个区间的两个端点处的差分有了变化，区间开始端点的差分增加了 3，区间结束端点后一个数据差分减少了 3 。

这个规律也容易得到，对原数据某个区间范围的数据统一修改（增减），从差分的角度来看，统一修改的区间范围内，因为大家增或减都是一致的，所以差不会变，只有在两个端处的差才会变。

我们正是利用差分这个特点，将对某个区间内的所有数据的修改转换为对差分数组这个区间的两个端点进行修改，复杂度一下就降低了。对差分数组修改完成后，再通过差分数组的前缀和是原数组这个性质，还原回去。

利用差分去处理某个区间修改的步骤为：

1. 预处理得到差分数组
2. 对差分数组指定区间的端点进行增减处理
3. 将修改后的差分数组再通过求前缀和还原回去，得到修改后的数组

参考代码如下：

#include <bits/stdc++.h>
using namespace std;

int n, k, l, m, x;
int q[110], diff[110];
int main() {
  cin >> n >> k;
  
  for (int i = 1; i <= n; i++) cin >> q[i];
  
  // 预处理得到差分数组
  for (int i = 1; i <= n; i++) {
    diff[i] = q[i] - q[i - 1];
  }
  
  while (k--) {
    cin >> l >> m >> x;
    // 对差分数组指定区间的端点进行处理
    diff[l] += x;
    diff[m + 1] -= x;
  }

  // 对差分数组求前缀和，还原回去
  for (int i = 1; i <= n; i++) {
    q[i] = q[i - 1] + diff[i];
  }
  
  // 按要求输出修改后的数组数据
  for (int i = 1; i <= n; i++) {
    cout << q[i] << " ";
  }
  
  return 0;
}

#差分的优点与应用

优点：

• 区间修改快：计算初始的差分数组需要 $O(n)$ 时间，但每次对 [L, R] 区间进行增减操作只需要 $O(1)$ 的时间。
• 概念巧妙：将区间的操作巧妙的转换为对两侧的端点操作

缺点：

• 朴素的解法虽然效率上稍差些，但理解上很简单，学过循环和数组的同学应该都能完成；相比之间，差分技巧虽然从效率上更高，但从理解上确实更难一些。
• 如果要查询修改过程中某个点的具体值或某个区间的和，差分数组本身不能直接给出答案，需要先从差分数组还原出原数组，才能得到结果

应用：

• 针对需要频繁对数组进行区间增减操作的场景，差分更适合

#总结

你可能已经注意到了，前缀和与差分在某种意义上是 互逆 的运算。

• 前缀和 主要用于 快速查询区间和。
• 差分 主要用于 快速处理区间修改。

理解它们各自解决的问题和实现方式，就能在合适的场景下选用合适的技巧，提高程序的效率。