一、前缀和与差分：从暴力到 O(1) 的思维跃迁

说实话，我刚入行那会儿，遇到「区间求和」这类问题，第一反应就是写个 for 循环。直到有一次在线上系统里，一个 O(n²) 的查询把数据库拖垮了……嗯，从那以后，我彻底记住了前缀和这个老朋友。

前缀和与差分，说白了就是「空间换时间」的经典套路。它们解决的是两类对称问题：快速求区间和 和 快速做区间更新。你想想看，如果每次查询都要遍历整个区间，数据量一大就崩了。但如果我们提前算好「累积值」，查询就变成了 O(1)。

1.1 一维前缀和

先看最简单的场景。给你一个数组 nums，频繁询问 sum(l, r)。暴力做法是每次循环累加，但前缀和的做法是：

// 预处理
int[] pre = new int[n + 1];
for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + nums[i - 1];
}

// 查询 [l, r] 区间和（0-indexed）
int rangeSum = pre[r + 1] - pre[l];

为什么下标从 1 开始？我个人习惯这样写，因为 pre[0] = 0 可以统一处理边界，避免一堆 if 判断。你在面试里也这么写，面试官一看就知道你懂细节。

1.2 二维前缀和

二维的情况稍微绕一点，但原理完全一样。我记得有一次做图像处理项目，需要快速计算任意矩形区域的像素和，二维前缀和直接让性能提升了两个数量级。

公式推导其实就一句话：容斥原理。

// 预处理
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];
    }
}

// 查询 (r1, c1) 到 (r2, c2) 的矩形和
int sum = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] 
        - pre[r2 + 1][c1] + pre[r1][c1];

你仔细看，其实就是「大矩形 - 两个小矩形 + 重叠部分」。这个图我画一下，你一看就懂。

1.3 差分数组

差分是前缀和的「逆运算」。前缀和解决「多次查询、一次构建」的问题，差分解决「一次查询、多次更新」的问题。

场景是这样的：给你一个数组，要做 大量区间加/减操作，最后才查询结果。如果每次操作都遍历区间，复杂度 O(nk)。差分数组可以把每次操作降到 O(1)。

// 差分数组
int[] diff = new int[n + 1];

// 对区间 [l, r] 加上 val
void add(int l, int r, int val) {
    diff[l] += val;
    diff[r + 1] -= val;
}

// 最后还原原数组
int[] res = new int[n];
int cur = 0;
for (int i = 0; i < n; i++) {
    cur += diff[i];
    res[i] = cur;
}

原理很简单：差分数组记录了「变化量」。前缀和还原时，累加变化量就得到了最终值。你想想看，是不是和微积分里的「导数→原函数」一个道理？

1.4 经典例题

例1：区域和检索 - 数组不可变

LeetCode 303 题。这题就是前缀和的模板题，没有任何弯弯绕绕。直接上代码：

class NumArray {
    private int[] pre;
    
    public NumArray(int[] nums) {
        pre = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return pre[right + 1] - pre[left];
    }
}

这题我面试时经常用来考察候选人的基本功。能写出 O(1) 查询的，说明对「预处理」有感觉；还在循环里求和的，嗯……需要再练练。

例2：航班预订统计

LeetCode 1109 题。这题是差分数组的经典应用。有 n 个航班，给你一堆预订记录 [l, r, seats]，最后返回每个航班的座位数。

public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n + 1];
    
    for (int[] booking : bookings) {
        int l = booking[0] - 1;  // 转为 0-indexed
        int r = booking[1] - 1;
        int seats = booking[2];
        
        diff[l] += seats;
        diff[r + 1] -= seats;
    }
    
    int[] res = new int[n];
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur += diff[i];
        res[i] = cur;
    }
    return res;
}

注意这里下标转换：题目给的是 1-indexed，我们内部用 0-indexed。我曾经在项目里因为下标没对齐，debug 了整整一下午……所以现在每次写差分，我都会在注释里标清楚「l 和 r 是闭区间」。

1.5 知识体系总览

下面这张图总结了前缀和与差分的核心脉络，你可以把它当作「速查地图」：

1.6 避坑指南与个人经验

• 下标越界： 差分数组长度一定要是 n+1，否则 r+1 可能越界。我见过太多人在这里翻车。
• 二维前缀和的初始化： 先算 pre[1][1]，再逐行逐列填充。别想着一步到位，容易乱。
• 差分还原时： 记得用 cur += diff[i]，不是 cur = diff[i]。这个错误我犯过两次，第一次是刚学的时候，第二次是熬夜加班的时候……
• 什么时候用前缀和，什么时候用差分？ 简单判断：查询多、更新少 → 前缀和；更新多、查询少 → 差分。如果两者都多，那就得上线段树或树状数组了。

好了，这一章的内容就到这里。前缀和与差分是算法设计里最基础、最实用的模式之一。你把它吃透了，后面学线段树、树状数组、甚至动态规划里的区间 DP，都会轻松很多。

---

公众号：蓝海资料掘金营，微信 deep3321