一维差分与前缀和：区间操作的加速器

说实话，刚学C语言那会儿，我遇到数组区间求和的问题，第一反应就是写个循环。一次两次还行，可要是几千次、几万次操作呢？程序直接卡成PPT。后来我接触了差分和前缀和这两个工具，才明白什么叫「四两拨千斤」。

今天咱们就聊聊这两个东西。它们不是啥高深算法，说白了就是预处理的思想——提前算好一些数据，后面直接用，省得每次都从头跑一遍。

前缀和：区间求和的「作弊器」

先看个场景。你有一个数组 arr[5] = {3, 1, 4, 1, 5}，现在要反复问：从第2个元素到第4个元素的和是多少？

常规做法：每次循环累加。但如果你先算一个前缀和数组 prefix，事情就简单了。

// 构建前缀和数组
int arr[] = {3, 1, 4, 1, 5};
int prefix[6];  // 多开一个位置，方便处理边界
prefix[0] = 0;
for (int i = 1; i <= 5; i++) {
    prefix[i] = prefix[i-1] + arr[i-1];
}
// 现在 prefix[3] 表示前3个元素的和：3+1+4=8
// 求 arr[1] 到 arr[3] 的和（下标从0开始）：
// 就是 prefix[4] - prefix[1] = (3+1+4+1) - (3) = 6

你看，区间 [l, r] 的和，直接等于 prefix[r+1] - prefix[l]。一次减法搞定，O(1) 时间。这就是前缀和的精髓——用空间换时间。

我在项目中遇到过一个问题：需要实时统计过去24小时的用户访问量。每次查询都遍历一遍？服务器扛不住。用前缀和预处理后，查询时间从O(n)降到了O(1)，效果立竿见影。

差分数组：区间修改的「批处理」

前缀和解决的是「多次查询」问题。那如果需求变成「多次修改」呢？比如给数组的某个区间统一加上一个值，然后才查询。

你想想看，每次修改都遍历区间，复杂度是O(n)。如果修改m次，就是O(m*n)。数据量一大，直接爆炸。

差分数组就是干这个的。它记录的是相邻元素的差值。

// 原数组
int arr[] = {3, 1, 4, 1, 5};
// 构建差分数组 diff
int diff[5];
diff[0] = arr[0];
for (int i = 1; i < 5; i++) {
    diff[i] = arr[i] - arr[i-1];
}
// 现在 diff = {3, -2, 3, -3, 4}

差分数组有个神奇的性质：对原数组的区间 [l, r] 加上一个值 x，只需要修改差分数组的两个位置：diff[l] += x，diff[r+1] -= x。

为什么？因为差分数组记录了变化量。在 l 处加 x，相当于从 l 开始所有元素都加了 x；在 r+1 处减 x，相当于从 r+1 开始恢复原状。一加一减，区间 [l, r] 就单独加了 x。

前缀和与差分的关系

其实这两个东西是互逆的。前缀和数组的差分就是原数组，差分数组的前缀和也是原数组。你中有我，我中有你。

我画了一张图，帮你理清它们的关系：

实战：区间修改 + 区间查询

单独用前缀和或差分，只能解决一半问题。要是既要多次修改，又要多次查询呢？

我建议的做法是：先用差分数组处理所有修改，最后一次性还原成原数组，再用前缀和去查询。这样修改和查询都是O(1)，整体复杂度O(n+m)。

#include <stdio.h>

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = 8;
    int diff[9] = {0};  // 多开一个

    // 第一次修改：区间 [1, 4] 加 2
    diff[1] += 2;
    diff[5] -= 2;

    // 第二次修改：区间 [3, 6] 加 3
    diff[3] += 3;
    diff[7] -= 3;

    // 还原数组
    int new_arr[8];
    new_arr[0] = arr[0] + diff[0];
    for (int i = 1; i < 8; i++) {
        diff[i] += diff[i-1];  // 差分数组求前缀和
        new_arr[i] = arr[i] + diff[i];
    }

    // 构建前缀和
    int prefix[9];
    prefix[0] = 0;
    for (int i = 1; i <= 8; i++) {
        prefix[i] = prefix[i-1] + new_arr[i-1];
    }

    // 查询区间 [2, 5] 的和
    int l = 2, r = 5;
    int sum = prefix[r+1] - prefix[l];
    printf("区间 [%d, %d] 的和为：%d\n", l, r, sum);

    return 0;
}

二维前缀和：扩展到矩阵

一维搞定了，二维其实同理。求子矩阵的和，用二维前缀和。

// 二维前缀和构建
int matrix[3][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
int prefix[4][5] = {0};
for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 4; j++) {
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] 
                     - prefix[i-1][j-1] + matrix[i-1][j-1];
    }
}
// 查询子矩阵 (x1,y1) 到 (x2,y2) 的和
// sum = prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1]

公式看着复杂，其实原理就是容斥原理。画个图就明白了：大矩形减去左边、上边，再加回重复减掉的左上角。

总结一下

前缀和和差分，说白了就是「预处理」的两种形式。一个存累计值，一个存变化量。它们解决的是两类问题：

• 前缀和：多次查询区间和，O(1) 搞定
• 差分：多次修改区间值，O(1) 搞定
• 组合使用：先差分修改，再前缀和查询，两全其美

我个人觉得，这两个工具是C语言数组处理的「基本功」。很多看似复杂的问题，比如图像处理中的区域亮度调整、游戏中的地图更新，底层用的都是这个思路。掌握了它们，你写代码的底气会足很多。

---

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