前缀和与差分数组：区间问题的端点思维

如果只看定义，“前缀和与差分数组：区间问题的端点思维”并不一定显得难。我当时真正卡住的是：我以前遇到区间求和就重复遍历，遇到区间修改又逐个更新，代码能跑但数据一大就完全扛不住。这次整理没有刻意追求一次讲完所有技巧，而是把我最容易断掉的几个理解环节重新接上。

前缀和与差分数组是一对非常实用的技巧。它们都不是复杂算法，却经常把看起来很慢的区间问题变得很干净。

简单说：

前缀和适合频繁区间查询。
差分数组适合频繁区间修改。

它从哪里来

累计和来自统计与制表中的长期实践：先保存从开头到当前位置的总量，就能用两次相减得到任意区间。差分则反过来记录相邻变化。程序设计把这对互逆表示用于高频区间查询和批量区间修改。

一查一改，两种方向

前缀和与差分数组

图：前缀和把区间求和变成两个端点相减，差分把区间修改变成两个端点变化

前缀和保存的是“从开头累加到当前位置”的结果。
差分保存的是“当前位置相对前一个位置变化了多少”。

这两个概念互为转换：

prefix[i + 1] = prefix[i] + nums[i]
nums[i] = diff[0] + diff[1] + ... + diff[i]

一维前缀和

给定数组 nums，多次查询区间 [l, r] 的和。如果每次都遍历区间，单次是 O(n)。前缀和可以把查询变成 O(1)。

class NumArray {
    private final int[] prefix;

    NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

为什么 prefix 要多开一位？因为这样 left = 0 时也能统一写成 prefix[right + 1] - prefix[left]，不用特殊判断。

二维前缀和

二维前缀和适合矩阵区域求和。

int[][] buildPrefix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] pre = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1]
                    - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
        }
    }
    return pre;
}

int sumRegion(int[][] pre, int r1, int c1, int r2, int c2) {
    return pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1]
            - pre[r2 + 1][c1] + pre[r1][c1];
}

二维公式里最容易忘的是减掉重复计算的左上角区域。

差分数组

如果有很多次区间加法，最后查询结果，差分数组很好用。

对区间 [l, r] 加 delta：

diff[l] += delta
diff[r + 1] -= delta

最后做一次前缀和还原。

int[] rangeAdd(int n, int[][] updates) {
    int[] diff = new int[n + 1];
    for (int[] u : updates) {
        int l = u[0], r = u[1], delta = u[2];
        diff[l] += delta;
        if (r + 1 < n) diff[r + 1] -= delta;
    }
    int[] ans = new int[n];
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur += diff[i];
        ans[i] = cur;
    }
    return ans;
}

差分的妙处在于，它不直接改区间里的每个值，而是记录“从哪里开始变化、从哪里结束变化”。

什么时候不用它

前缀和适合静态数组。如果中间频繁修改单个元素，普通前缀和每次修改都要影响后面所有位置，成本很高。这时可以考虑树状数组或线段树。

差分适合“批量区间修改，最后统一查询”。如果修改和查询交替进行，也应该考虑树状数组、线段树或平衡树结构。

工程场景

统计一段时间内的访问量。
统计日志区间内的错误数。
批量给用户积分区间加成。
日程系统统计会议室占用。
游戏中地图区域增益。
活动期间按时间段叠加优惠。

在工程中，前缀和常和时间桶一起使用。比如把一天切成分钟粒度，统计每分钟请求量后，就能快速查询任意时间段的总量。

常见错误

区间是闭区间还是半开区间没说清。
前缀数组下标和原数组下标混乱。
二维前缀和忘记加回左上角。
差分数组忘记判断 r + 1 越界。
使用 int 导致大数据求和溢出，此时应使用 long。

面试题

为什么一维前缀和数组通常多开一位？
二维前缀和公式为什么要减两块再加一块？
差分数组为什么只改两个端点？
前缀和不适合频繁修改的原因是什么？
如果既频繁修改又频繁查询，应该考虑什么结构？

小结

前缀和与差分数组都是“把重复工作提前或延后”的技巧。前缀和提前把累计结果算好，差分延后把批量修改统一还原。理解它们以后，很多区间题会从暴力枚举变成清爽的端点操作。