成长之路

差分数组

什么是差分数组

差分数组是一种有效记录数组连续部分和变化的数据结构。 对于给定的数组 \(a[0], a[1], ... , a[n]\)，我们定义差分数组 \(diff\) 为 \(diff[i] = a[i] - a[i - 1]\)，其中 \(i\) 从\(1\) 至 \(n\)，特殊地，\(diff[0] = a[0]\)。

例如，给定数组 \([1, 2, 4, 7, 8]\)，它的差分数组就是 \([1, 1, 2, 3, 1]\)

应用

差分数组还有很多其他的应用，例如在处理一些区间修改的问题上，比如线段树，树状数组等，差分思想相比于它们来说更加直观，实现起来也更简单。

case

当我们要对原数组的一个连续的区间 \([l, r]\) 内的所有元素进行加法或者减法操作时，只需要对对应的差分数组 \([l, r]\) 做三次操作，而不需要遍历整个区间。步骤如下：
1. 如果我们需要对区间 \([l, r]\) 的元素全部加上 \(k\)，\(diff[l] += k\)
2. 如果\(r + 1 < n + 1\) 则 \(diff[r + 1] -= k\) 。
3. 然后，获取更新后的原数组，可以通过 \(diff\) 数组的前缀和恢复出 \(m\) 数组。公式是 \(a[i] = diff[1] + diff[2] + ... + diff[i]\) ，其中 \(1 <= i <= n\)，\(a[0] = diff[0]\)。

公式

构造diff

\[ \begin{align*} \text{diff}[i] = \begin{cases} a[0], & \quad i=0 \\ \text{diff}[i] = a[i] - a[i - 1], & \quad 0 < i < \text{a.length} \end{cases} \tag{1.1} \end{align*} \]

区间l到r增加k

\[ \begin{align*} \text{diff}[l] & += k, \quad 0 \leq k < \text{diff.length} \\ \text{diff}[r + 1] & -= k, \quad \text{if}\quad r + 1 < \text{diff.length} \tag{1.2} \end{align*} \]

还原diff

\[ \begin{equation} a[i] = \begin{cases} 0, & \text{if}\ \ i = 0,\ \\ a[i - 1] + diff[i], \ \ &\text{for}\ 1 \leq i \leq n \end{cases} \tag{1.3} \end{equation} \]

模板

public class Difference {
    private final int[] diff;

    public Difference(int[] nums) {
        diff = new int[nums.length];

        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    public void increment(int left, int right, int val) {
        diff[left] += val;
        if (right + 1 < diff.length) {
            diff[right + 1] -= val;
        }
    }

    public int[] getRes() {
        int[] res = new int[diff.length];
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }

        return res;
    }
}

实战

航班预定

拼车