第26章前缀和与差分

课程目录第26章前缀和与差分

第26章前缀和与差分：区间问题的利器

说实话，我刚入行那会儿，最怕的就是区间操作。动不动就O(n²)的复杂度，数据量一大直接卡死。后来我师父扔给我一句话：「小子，学会前缀和和差分，你的代码能快十倍。」

今天咱们就把这两个东西彻底讲透。它们其实是一对「镜像」操作——前缀和用来快速查询区间和，差分用来快速修改区间值。你想想看，是不是很对称？

一维前缀和：从暴力到O(1)查询

先看最基础的问题：给定一个数组a[1..n]，频繁询问区间[l, r]的和。暴力做法每次遍历，复杂度O(n)。如果问m次，就是O(n*m)。

前缀和的思想很简单：预处理一个数组S，其中S[i] = a[1] + a[2] + ... + a[i]。那么区间[l, r]的和 = S[r] - S[l-1]。

核心公式：sum[l, r] = prefix[r] - prefix[l-1]

// 一维前缀和 - 预处理
int a[N], prefix[N];
for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i-1] + a[i];
}

// 查询区间[l, r]的和
int query(int l, int r) {
    return prefix[r] - prefix[l-1];
}

我的习惯：数组下标从1开始，这样prefix[0]=0，处理边界时不用特判。这个习惯我用了十几年，从来没出过边界bug。

二维前缀和：扩展到矩阵

二维的情况其实就是一个容斥原理。假设我们有一个矩阵a，想快速求子矩阵(x1,y1)到(x2,y2)的和。

预处理公式：prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + a[i][j]

查询公式：sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]

// 二维前缀和 - 预处理
int a[N][N], prefix[N][N];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] 
                     - prefix[i-1][j-1] + a[i][j];
    }
}

// 查询子矩阵和
int query(int x1, int y1, int x2, int y2) {
    return prefix[x2][y2] - prefix[x1-1][y2] 
         - prefix[x2][y1-1] + prefix[x1-1][y1-1];
}

我曾经踩过的坑：二维前缀和的下标偏移特别容易搞混。我的建议是——先在纸上画个2x2的小矩阵，手动算一遍，再写代码。别问我为什么知道，问就是当年debug到凌晨三点。

差分数组：区间修改的「反向操作」

前缀和解决的是「多次查询、静态数组」的问题。那如果我们要「多次修改、一次查询」呢？比如给区间[l, r]每个数都加上c，最后才看结果。

差分数组就是干这个的。定义diff[i] = a[i] - a[i-1]（a[0]=0）。对区间[l, r]加c，只需要：diff[l] += c, diff[r+1] -= c。最后对diff求前缀和，就还原出原数组。

// 差分数组 - 区间修改
int diff[N];  // 初始全0

// 对区间[l, r]每个数加c
void add(int l, int r, int c) {
    diff[l] += c;
    diff[r+1] -= c;
}

// 最后还原原数组
for (int i = 1; i <= n; i++) {
    a[i] = a[i-1] + diff[i];
}

本质理解：差分是前缀和的逆运算。前缀和把数组变成「累积和」，差分把数组变成「变化量」。两者配合，可以解决绝大多数区间问题。

二维差分：矩阵区间修改

二维差分和一维的思路完全一样，只是多了一个维度。对子矩阵(x1,y1)到(x2,y2)每个数加c：

// 二维差分 - 区间修改
void add(int x1, int y1, int x2, int y2, int c) {
    diff[x1][y1] += c;
    diff[x1][y2+1] -= c;
    diff[x2+1][y1] -= c;
    diff[x2+1][y2+1] += c;
}

// 最后还原原矩阵
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        a[i][j] = a[i-1][j] + a[i][j-1] 
                - a[i-1][j-1] + diff[i][j];
    }
}

知识体系总览

下面这张图把本章的核心逻辑串起来了，我建议你多看几遍：

典型应用：差分 + 前缀和组合拳

实际项目中，这两个东西经常一起用。我记得有一次做传感器数据采集，需要频繁对某个时间段的数据做整体偏移，最后又要统计每个时间点的最终值。差分做修改，前缀和做查询，完美配合。

举个具体例子：

// 场景：有n个任务，每个任务在[l, r]时间段内执行，求每个时间点有多少任务在执行
// 思路：差分标记 + 前缀和还原

int diff[N];  // 差分数组

for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    diff[l] += 1;
    diff[r+1] -= 1;
}

// 前缀和还原
for (int i = 1; i <= n; i++) {
    diff[i] += diff[i-1];
    printf("时间点%d有%d个任务\n", i, diff[i]);
}

避坑指南：差分数组的边界处理一定要小心。r+1可能越界，所以数组要开大一点。我一般开N+5，留足余量。

复杂度对比

操作	暴力法	前缀和/差分	优化效果
一维区间求和	O(n) / 次	O(1) / 次	快n倍
二维子矩阵求和	O(n*m) / 次	O(1) / 次	快n*m倍
一维区间修改	O(n) / 次	O(1) / 次	快n倍
二维区间修改	O(n*m) / 次	O(1) / 次	快n*m倍

说白了，前缀和和差分就是拿预处理的时间，换查询/修改的时间。在数据量大、操作频繁的场景下，这笔买卖绝对划算。

注意：前缀和和差分只适合「静态查询」或「批量修改后一次性查询」的场景。如果边修改边查询，那就得用线段树或树状数组了。别用错地方，否则反而更慢。

好了，这一章的内容就到这里。记住一句话：前缀和管查询，差分管修改，两者是镜像关系。搞懂了这一点，区间问题就不再是难题。

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

📚 课程目录