差分数组

2025-02-02

字数统计: 1k字 | 阅读时长: 4分

前言

差分数组利用空间换时间，实现在$O(1)$时间内完成对连续数组的增减操作。本次介绍一维、二维差分数组。

需要注意的是，差分数组对于查询频繁的场景并不适用，因为还原数组仍需全部遍历。

引出

考虑数组 $a=[1,3,3,5,8]$，对其中的相邻元素两两作差（右边减左边），得到数组 $[2,0,2,3]$。然后在开头补上 $a[0]$，得到差分数组：$d=[1,2,0,2,3]$

这有什么用呢？如果从左到右累加 ddd 中的元素，我们就「还原」回了 $a$ 数组 $[1,3,3,5,8]$。这类似求导与积分的概念。

这又有什么用呢？现在把连续子数组 $a[1],a[2],a[3]$ 都加上 $10$，得到 $a’=[1,13,13,15,8]$。再次两两作差，并在开头补上 $a’[0]$，得到差分数组：$d’=[1,12,0,2,−7]$

对比 $d$ 和 $d’$，可以发现只有 $d[1]$ 和 $d[4]$ 变化了，这意味着对 $a$ 中连续子数组的操作，可以转变成对差分数组 $d$ 中两个数的操作。

定义和性质

对于数组 $a$，定义其差分数组（difference array）为

$d[i] = \begin{cases} a[0],&i=0\\ a[i]-a[i-1],&i\ge 1 \end{cases} $

性质 1：从左到右累加 $d$ 中的元素，可以得到数组 $a$。

性质 2：如下两个操作是等价的。

把 $a$ 的子数组 $a[i],a[i+1],\cdots,a[j]$ 都加上 $x$。
把 $d[i]$ 增加 $x$，把 $d[j+1]$ 减少 $x$。

利用性质 2，我们只需要 $O(1)$ 的时间就可以完成对 $a$ 的子数组的操作。最后利用性质 1 从差分数组复原出数组 $a$。

注：也可以这样理解，$d[i]$ 表示把下标 $≥i$ 的数都加上 $d[i]$。

二维差分数组

对于二维数组 a，可以将其定义为差分数组 d 的二维前缀和数组。差分数组的每个元素 d[i][j] 反映了原数组中特定区域的增量变化，满足以下关系：

$a[i][j] = \sum_{x=0}^i \sum_{y=0}^j d[x][y]$

构造差分数组时，初始化全为0。对原数组 a 的子矩阵操作（从 (x1,y1) 到 (x2,y2) 加 x）可转换为对差分数组 d 的四个关键点的操作：

d[x1][y1] += x
d[x1][y2+1] -= x
d[x2+1][y1] -= x
d[x2+1][y2+1] += x

这样，在后续计算前缀和时，该子矩阵内的所有元素都会正确增加 x。通过计算差分数组的二维前缀和即可还原出原数组。每个元素的值由其左上方的差分值累加得到。

示例代码如下：

public class TwoDDifference {
    private int[][] d;
    private int m;
    private int n;

    // 构造函数：根据原数组构造差分数组
    public TwoDDifference(int[][] a) {
        m = a.length;
        n = a[0].length;
        d = new int[m + 1][n + 1]; // 多开一行一列处理边界
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 将每个元素的初始化视为单点更新
                add(i, j, i, j, a[i][j]);
            }
        }
    }

    // 对子矩阵 [x1,y1] 到 [x2,y2] 增加 x
    public void add(int x1, int y1, int x2, int y2, int x) {
        d[x1][y1] += x;
        d[x1][y2 + 1] -= x;
        d[x2 + 1][y1] -= x;
        d[x2 + 1][y2 + 1] += x;
    }

    // 计算并返回操作后的原数组
    public int[][] compute() {
        int[][] a = new int[m][n];
        // 计算二维前缀和
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = d[i][j];
                if (i > 0) a[i][j] += a[i - 1][j];
                if (j > 0) a[i][j] += a[i][j - 1];
                if (i > 0 && j > 0) a[i][j] -= a[i - 1][j - 1];
            }
        }
        return a;
    }
}

使用示例：

int[][] original = {{1, 2}, {3, 4}};
TwoDDifference diff = new TwoDDifference(original);
diff.add(0, 0, 1, 1, 5); // 整个矩阵加 5
int[][] result = diff.compute(); 
// 结果变为 [[6,7], [8,9]]

参考文献

[1] https://silencezheng.top/2024/08/18/article133/
[2] https://blog.csdn.net/qq_63786973/article/details/127667301

后记

首发于 silencezheng.top，转载请注明出处。