一维差分

本篇对应源码见仓库 solutions/xcpc/algorithm/prefix/difference/。

一、线性差分（Difference Array）

1.1 原理概述

对于长度为 $n$ 的数组 A[1..n]，若需要对若干区间 $[l_i,r_i]$ 做“加值 $v_i$” 操作，常规做法每次 $O(r_i-l_i+1)$，总复杂度易至 $O(nQ)$。差分技巧将「区间加」和「前缀和」结合：

• 维护差分数组 D[1..n+1]，初始全 0；

• 对每次区间操作 “$A[l..r]$ 每个元素加 $v$”：

  D[l]   += v;
  D[r+1] -= v;

• 操作结束后，恢复原数组：

  for (int i = 1; i <= n; i++) {
      D[i] += D[i-1];
      A[i] += D[i];
  }

这样每次区间操作 $O(1)$，最终一次 $O(n)$ 前缀和遍历即可完成所有修改。

1.2 常见变体

• 点修改 + 区间查询：直接维护原数组前缀和即可；

• 区间修改 + 点查询：使用如上差分；

• 区间修改 + 区间查询：可再套一层「差分的差分」，或用线段树 / 树状数组。

1.3 代码模板（C++17）

signed main() {
    IOS;

    int n, p;
    cin >> n >> p;
    vector<int> a(n + 1);
    fer(i, 1, n + 1) {
    	cin >> a[i];
    }
    // 差分数组长度比原数组大 1
    vector<int> diff(n + 2);
    while(p--) {
    	int l, r, d;
    	cin >> l >> r >> d;
    	diff[l] += d, diff[r + 1] -= d;
    }
    int ans = inf;
    fer(i, 1, n + 1) {
	    // 差分的前缀和，相当于计算出原数组的元素需要的偏移量
    	diff[i] += diff[i - 1];
    	a[i] += diff[i];
    	ans = min(ans, a[i]);
    }
    cout << ans << '\n';

    return 0;
}