差分

约 779 字大约 3 分钟

算法离散差分

2025-02-09

引入

差分是快速处理区间加减操作的算法。它是前缀和的逆运算。

提示

为什么称为逆运算

因为我们对一个数组进行前缀和后，再进行一次差分，就可以得到原数组，反过来也一样。

它的计算公式为

d_i= \begin{cases} a_i,&i=0 \\ a_i-a_{i-1},&i>0 \end{cases}

具体写法如：

for (int i = n - 1; i >= 0; i--) {
    if (i == 0) d[i] = a[i];
    else d[i] = a[i] - a[i - 1];
}

在C++的标准库中，也有

adjacent_difference(a.begin(), a.end(), d.begin());

深入

主要推论

a[l,r]+k \iff d[l]+k, d[r+1]-k

等式左侧对应在区间 $(l,r)$ 多个位置进行运算，如果进行 $M$ 次这样的操作，最坏时间复杂度达到 $O(N \cdot M)$

如果我们进行等式右侧的操作，每次只用在 $l$ , $r+1$ 两个位置进行运算，如果进行 $M$ 次这样的操作，最坏时间复杂度达到 $O(N + M)$ ，大大降低了时间复杂度，因此称为快速处理区间加减操作的算法。

二维运算

在二维数组中，差分的计算方法可以为

diff.cpp

auto d = vector(n + 1, vector<int>(m + 1));

for (int i = n; i >= 1; i--) {
    for (int j = m; j >= 1; j--) {
        d[i][j] = a[i][j] - a[i - 1][j];
    }
    adjacent_difference(d[i].begin(), d[i].end(), d[i].begin());
}

for (int i = n; i >= n; i--) {
    for (int j = m; j >= 1; j--) {
        d[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
    }
}

prefix.cpp

auto a = vector(n, vector<int>(m));
auto sum = vector(n + 1, vector<int>(m + 1));

// 先考虑current row，再加上上一行的影响
for (int i = 1; i <= n; i++) {
    partial_sum(a.begin(), a.end(), sum[i].begin());
    for (int j = 1; j <= m; j++) {
        sum[i][j] += sum[i - 1][j];
    }
}

// 根据周边的几块，利用容斥原理
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        sum[i][j] =
            a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    }
}