每日算法 — 使用java实现差分数组：区间更新与前缀和还原

差分数组（Difference Array）是一种高效处理区间更新的技巧。当需要对数组的某个区间 [l, r] 内的所有元素同时加上一个值 v 时，暴力方法需要 O(r-l+1) 时间，而差分数组只需 O(1) 时间。本文用Java实现差分数组，讲解其原理、区间更新操作与前缀和还原，并结合实际例题展示应用场景。

核心原理

差分数组 diff 与原数组 arr 的关系：

diff[0] = arr[0]
diff[i] = arr[i] - arr[i-1]  (i > 0)

反过来，原数组可以通过前缀和还原：

arr[i] = diff[0] + diff[1] + ... + diff[i]

关键性质：对原数组区间 [l, r] 每个元素加 v，等价于：
– diff[l] += v
– diff[r+1] -= v（如果 r+1 在范围内）

这样单次区间更新仅需两次单点修改，复杂度为 O(1)。

为什么差分数组有效

原数组:     [3,  3,  3,  3,  3,  3]
差分数组:   [3,  0,  0,  0,  0,  0]

对[1,3]加2:
diff[1] += 2 → [3,  2,  0,  0,  0,  0]
diff[4] -= 2 → [3,  2,  0,  0, -2,  0]

前缀和还原: [3, 5, 5, 5, 3, 3]
              ↑  ↑  ↑
            只有这三个位置增加了2

Java完整实现

import java.util.Arrays;

/**
 * 差分数组（Difference Array）
 * 高效处理区间更新，单次更新O(1)，最终还原O(n)
 */
public class DifferenceArray {

    private long[] diff;    // 差分数组
    private int n;          // 数组长度

    /**
     * 从原数组构建差分数组
     */
    public DifferenceArray(int[] arr) {
        this.n = arr.length;
        this.diff = new long[n];
        diff[0] = arr[0];
        for (int i = 1; i < n; i++) {
            diff[i] = arr[i] - arr[i - 1];
        }
    }

    /**
     * 区间更新：对[l, r]区间内每个元素加上value
     * 时间复杂度: O(1)
     */
    public void rangeAdd(int l, int r, long value) {
        if (l < 0 || r >= n || l > r) {
            throw new IllegalArgumentException("无效的区间范围");
        }
        diff[l] += value;
        if (r + 1 < n) {
            diff[r + 1] -= value;
        }
    }

    /**
     * 单点更新：对位置idx加上value
     * 等价于 rangeAdd(idx, idx, value)
     */
    public void pointAdd(int idx, long value) {
        rangeAdd(idx, idx, value);
    }

    /**
     * 前缀和还原：从差分数组还原出最终数组
     * 时间复杂度: O(n)
     */
    public long[] reconstruct() {
        long[] result = new long[n];
        result[0] = diff[0];
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }

    /**
     * 获取某个位置的当前值（不还原整个数组）
     * 时间复杂度: O(n)，若频繁查询建议先还原
     */
    public long getValue(int idx) {
        long sum = 0;
        for (int i = 0; i <= idx; i++) {
            sum += diff[i];
        }
        return sum;
    }

    /**
     * 打印差分数组（调试用）
     */
    public void printDiff() {
        System.out.println("差分数组: " + Arrays.toString(diff));
    }

    /**
     * ========== 二维差分数组 ==========
     * 用于矩阵的矩形区域更新
     */
    public static class Diff2D {
        private long[][] diff;
        private int rows, cols;

        public Diff2D(int rows, int cols) {
            this.rows = rows;
            this.cols = cols;
            this.diff = new long[rows + 2][cols + 2]; // 多开一圈避免越界判断
        }

        /**
         * 矩形区域更新：对[x1,y1]到[x2,y2]的矩形区域每个元素加value
         * 时间复杂度: O(1)
         */
        public void rangeAdd(int x1, int y1, int x2, int y2, long value) {
            diff[x1][y1] += value;
            diff[x2 + 1][y1] -= value;
            diff[x1][y2 + 1] -= value;
            diff[x2 + 1][y2 + 1] += value;
        }

        /**
         * 还原二维数组
         */
        public long[][] reconstruct() {
            long[][] result = new long[rows][cols];
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    long val = diff[i][j];
                    if (i > 0) val += result[i - 1][j];
                    if (j > 0) val += result[i][j - 1];
                    if (i > 0 && j > 0) val -= result[i - 1][j - 1];
                    result[i][j] = val;
                }
            }
            return result;
        }
    }

    public static void main(String[] args) {
        // ========== 一维差分数组演示 ==========
        System.out.println("=== 一维差分数组演示 ===");
        int[] arr = {0, 0, 0, 0, 0, 0, 0, 0};
        DifferenceArray da = new DifferenceArray(arr);
        da.printDiff();

        // 执行多次区间更新
        da.rangeAdd(1, 3, 5);   // [0, 5, 5, 5, 0, 0, 0, 0]
        da.rangeAdd(2, 5, 3);   // [0, 5, 8, 8, 3, 3, 0, 0]
        da.rangeAdd(0, 7, 1);   // [1, 6, 9, 9, 4, 4, 1, 1]
        da.rangeAdd(4, 4, 10);  // [1, 6, 9, 9, 14, 4, 1, 1]

        da.printDiff();
        long[] result = da.reconstruct();
        System.out.println("还原结果: " + Arrays.toString(result));

        // 验证
        System.out.println("验证:");
        System.out.println("  位置0: 0+1=1 ✓");
        System.out.println("  位置1: 0+5+1=6 ✓");
        System.out.println("  位置2: 0+5+3+1=9 ✓");
        System.out.println("  位置4: 0+3+1+10=14 ✓");

        // ========== 二维差分数组演示 ==========
        System.out.println("\n=== 二维差分数组演示 ===");
        Diff2D diff2d = new Diff2D(5, 5);

        // 在(1,1)到(3,3)区域加1
        diff2d.rangeAdd(1, 1, 3, 3, 1);
        // 在(2,2)到(4,4)区域加2
        diff2d.rangeAdd(2, 2, 4, 4, 2);

        long[][] matrix = diff2d.reconstruct();
        System.out.println("二维还原结果:");
        for (long[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }

        // ========== 经典例题：航班预订统计 ==========
        System.out.println("\n=== 例题：航班预订统计 ===");
        // bookings[i] = [first, last, seats] 表示从first到last航班预订seats个座位
        int[][] bookings = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}};
        int nFlights = 5;
        int[] answer = corpFlightBookings(bookings, nFlights);
        System.out.println("航班预订: " + Arrays.deepToString(bookings));
        System.out.println("每航班座位: " + Arrays.toString(answer));
        // 期望: [10, 55, 45, 25, 25]
    }

    /**
     * 经典例题：航班预订统计（LeetCode 1109）
     * 使用差分数组解决
     */
    public static int[] corpFlightBookings(int[][] bookings, int n) {
        long[] diff = new long[n + 2];

        // 所有预订转化为差分数组操作
        for (int[] booking : bookings) {
            int first = booking[0] - 1; // 转为0索引
            int last = booking[1] - 1;
            int seats = booking[2];
            diff[first] += seats;
            diff[last + 1] -= seats;
        }

        // 前缀和还原
        int[] result = new int[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += diff[i];
            result[i] = (int) sum;
        }
        return result;
    }

    /**
     * 进阶例题：拼车判断（LeetCode 1094）
     * 判断车辆容量是否足够承载所有乘客
     */
    public static boolean carPooling(int[][] trips, int capacity) {
        // 最多1000个站点
        long[] diff = new long[1001];

        for (int[] trip : trips) {
            int num = trip[0];
            int from = trip[1];
            int to = trip[2];
            diff[from] += num;
            diff[to] -= num; // 到to站点时乘客已下车
        }

        long current = 0;
        for (long d : diff) {
            current += d;
            if (current > capacity) {
                return false;
            }
        }
        return true;
    }
}

进阶应用：区间最值与差分约束

区间加法与单点查询

差分数组天然支持区间加法与单点查询。如果需求是”区间加、区间求和”，可以结合树状数组或线段树实现。

差分约束系统

差分数组的思想是差分约束系统的特例。对于不等式 x[i] - x[i-1] <= c，可以用最短路算法求解。差分数组则处理等式形式的约束。

复杂度分析

对于 m 次区间更新 + 1 次最终查询：
– 暴力方法：O(m · n)
– 差分数组：O(m + n)

当 m 很大时（如 10⁵ 次更新），差分数组的优势极其明显。

适用场景总结

差分数组最适合以下场景：

• 频繁区间更新，少量最终查询：如航班预订、教室占用统计
• 二维矩形区域更新：如图像处理中的区域加值、游戏地图的范围伤害
• 作为高级数据结构的基础：如线段树懒标记的底层原理就是差分思想
• 与前缀和配合使用：差分是前缀和的逆运算，两者常组合使用

掌握差分数组后，可以将 O(n) 的区间操作优化到 O(1)，是算法竞赛和工程开发中不可或缺的技巧。