前缀和与差分

区间查询与区间更新的优化技术

专题： 数据结构与算法基础

核心主题： 前缀和（Prefix Sum）与差分数组（Difference Array）

主要内容： 一维/二维前缀和、差分数组、二维差分、前缀和与哈希表结合、区间查询与区间更新的优化

关键词： 前缀和、差分数组、区间查询、区间更新、二维前缀和、差分、容斥原理

一、概述

前缀和（Prefix Sum）和差分数组（Difference Array）是算法竞赛与面试中极为重要的两种预处理技术。它们虽然实现简单，却能大幅优化区间查询与区间更新操作的时间复杂度，是"空间换时间"思想的经典体现。

前缀和的核心思想是：预处理出前缀和数组，使得任意区间和的查询在 O(1) 时间内完成。而差分数组则是前缀和的逆运算：通过构建差分数组，使得任意区间内的批量更新操作在 O(1) 时间内完成。两者互为逆过程，一个面向"查询"优化，一个面向"更新"优化，在实际问题中往往配合使用。

核心思想速览

前缀和： 预处理 O(n)，查询 O(1) — 解决"区间和"查询问题
差分数组： 更新 O(1)，恢复 O(n) — 解决"区间批量更新"问题
二维扩展： 利用容斥原理将一维思想推广到二维矩阵
哈希表结合： 前缀和 + 哈希表可以高效解决子数组统计问题

二、一维前缀和

2.1 定义

给定一个长度为 n 的数组 a[0..n-1]，定义其前缀和数组 prefix[0..n] 满足：

数学定义prefix[0] = 0
prefix[i] = a[0] + a[1] + ... + a[i-1] = prefix[i-1] + a[i-1],  i >= 1

即 prefix[i] 表示原数组前 i 个元素的和。这种定义方式（prefix 长度为 n+1，下标从 0 开始）在实现时最为便利，因为它统一了边界条件，无需处理空区间的特殊情况。

2.2 构建与查询

构建： 从左到右遍历一遍，时间复杂度 O(n)。

查询： 要查询区间 [l, r]（含端点）的和，结果为：

公式区间和 = prefix[r + 1] - prefix[l]

这是因为 prefix[r+1] = a[0] + ... + a[r]，而 prefix[l] = a[0] + ... + a[l-1]，二者相减恰好得到 a[l] + ... + a[r]。

2.3 代码模板

C++#include <vector>
using namespace std;

class PrefixSum {
private:
    vector<int> prefix;

public:
    // 构建前缀和数组 O(n)
    PrefixSum(vector<int>& nums) {
        int n = nums.size();
        prefix.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }

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

Pythonclass PrefixSum:
    def __init__(self, nums):
        n = len(nums)
        self.prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            self.prefix[i] = self.prefix[i - 1] + nums[i - 1]

    def range_sum(self, l, r):
        return self.prefix[r + 1] - self.prefix[l]

使用示例：

C++vector<int> nums = {1, 2, 3, 4, 5, 6};
PrefixSum ps(nums);
ps.rangeSum(1, 3);  // 2 + 3 + 4 = 9
ps.rangeSum(0, 5);  // 1 + 2 + 3 + 4 + 5 + 6 = 21

一维前缀和的特征

可逆性： 原数组可以通过相邻前缀和的差恢复：a[i] = prefix[i+1] - prefix[i]
可结合性： 多个前缀和的线性组合可以表达任意区间的和
不变性： 如果不修改原数组，每次查询都是严格 O(1)
局限性： 如果原数组频繁更新，每次更新后需要 O(n) 重建前缀和

三、二维前缀和

3.1 容斥原理

二维前缀和是将一维前缀和推广到二维矩阵上。对于一个 m x n 的矩阵 matrix，定义二维前缀和数组 prefix，其中 prefix[i][j] 表示从 (0,0) 到 (i-1,j-1) 的子矩阵中所有元素之和。

二维前缀和的递推式基于容斥原理：

递推公式prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1]

理解这个公式的关键在于：prefix[i-1][j] 覆盖了上方区域，prefix[i][j-1] 覆盖了左方区域，两者相加时左上角区域 prefix[i-1][j-1] 被重复计算了一次，因此需要减去一次，最后加上当前位置的元素值。

容斥原理图示

求 (r1,c1) 到 (r2,c2) 的子矩阵和：

    (r1,c1) ┌──────────┐ (r1,c2)
            │  目标区域  │
    (r2,c1) └──────────┘ (r2,c2)

公式：sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

减去的两项分别对应"上方区域"和"左方区域"，加回的一项对应被重复减去的"左上角区域"。

3.2 代码模板

C++#include <vector>
using namespace std;

class PrefixSum2D {
private:
    vector<vector<int>> prefix;

public:
    // 构建二维前缀和 O(m*n)
    PrefixSum2D(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        prefix.resize(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1]
                             - prefix[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    // 查询子矩阵 (r1,c1) 到 (r2,c2) 的和 O(1)
    int submatrixSum(int r1, int c1, int r2, int c2) {
        return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1]
             - prefix[r2 + 1][c1] + prefix[r1][c1];
    }
};

Pythonclass PrefixSum2D:
    def __init__(self, matrix):
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            row_sum = 0
            for j in range(1, n + 1):
                # 可进一步优化为逐行累加，减少重复计算
                self.prefix[i][j] = (self.prefix[i - 1][j]
                                   + self.prefix[i][j - 1]
                                   - self.prefix[i - 1][j - 1]
                                   + matrix[i - 1][j - 1])

    def submatrix_sum(self, r1, c1, r2, c2):
        return (self.prefix[r2 + 1][c2 + 1]
              - self.prefix[r1][c2 + 1]
              - self.prefix[r2 + 1][c1]
              + self.prefix[r1][c1])

典型题目：LeetCode 304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix，实现一个函数 sumRegion(row1, col1, row2, col2) 返回左上角 (row1, col1) 到右下角 (row2, col2) 的子矩阵元素之和。使用二维前缀和可以将每次查询从 O(m*n) 优化到 O(1)。

四、前缀和的应用

前缀和不仅用于查询区间和，在很多经典算法题中，前缀和与哈希表结合能够高效解决子数组相关的问题。

4.1 和为 k 的子数组

问题：给定一个整数数组 nums 和一个整数 k，统计并返回该数组中和为 k 的连续子数组的个数。（LeetCode 560. Subarray Sum Equals K）

核心思想： 子数组 [j..i] 的和等于 prefix[i+1] - prefix[j]。我们要求 prefix[i+1] - prefix[j] = k，即 prefix[j] = prefix[i+1] - k。因此遍历时用哈希表记录每个前缀和出现的次数，就可以在 O(1) 时间内找到满足条件的前缀和个数。

C++ LeetCode 560#include <unordered_map>
#include <vector>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    hash[0] = 1;          // 空前缀和出现一次
    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;       // 当前前缀和
        // 如果存在前缀和为 sum - k，则它们之间的子数组和为 k
        if (hash.count(sum - k))
            count += hash[sum - k];
        hash[sum]++;      // 记录当前前缀和
    }
    return count;
}

4.2 连续子数组和（倍数关系）

问题：给定一个整数数组 nums 和一个整数 k，判断是否存在长度为至少 2 的连续子数组，其和为 k 的倍数。（LeetCode 523. Continuous Subarray Sum）

核心思想： 如果两个前缀和对 k 取模的值相同（即 prefix[j] % k == prefix[i] % k），则子数组 [j..i-1] 的和是 k 的倍数。用哈希表记录每个余数第一次出现的位置，并确保子数组长度至少为 2。

C++ LeetCode 523#include <unordered_map>
#include <vector>
using namespace std;

bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    hash[0] = -1;         // 方便处理下标
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        int mod = k == 0 ? sum : sum % k;
        if (hash.count(mod)) {
            if (i - hash[mod] >= 2) return true;
        } else {
            hash[mod] = i;  // 只记录第一次出现的位置
        }
    }
    return false;
}

4.3 平衡数组（可被整除的最长子数组）

问题：给定一个整数数组 nums，找到最长的连续子数组，使得子数组内元素的和可以被数组长度整除的某个目标值 k 整除。

核心思想： 同样是利用前缀和取模的相等性。如果 prefix[i] % k == prefix[j] % k，那么子数组 [j..i-1] 的和可以被 k 整除。哈希表记录每个余数首次出现的位置，然后取最大距离。

C++#include <unordered_map>
#include <vector>
using namespace std;

int longestSubarrayDivByK(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    hash[0] = -1;
    int sum = 0, maxLen = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        int mod = ((sum % k) + k) % k;  // 处理负数取模
        if (hash.count(mod)) {
            maxLen = max(maxLen, i - hash[mod]);
        } else {
            hash[mod] = i;
        }
    }
    return maxLen;
}

4.4 除自身以外数组的乘积

问题：给定一个整数数组 nums，返回一个新数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。（LeetCode 238. Product of Array Except Self）

核心思想： 这本质上是"前缀积"与"后缀积"的结合。先从左到右计算每个位置的前缀积，再从右到左乘上后缀积，即可在 O(n) 时间和 O(1) 额外空间（不计输出数组）内完成。

C++ LeetCode 238#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);
    // 前缀积：answer[i] = nums[0] * ... * nums[i-1]
    for (int i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }
    // 后缀积：从右往左乘上 nums[i+1] * ... * nums[n-1]
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= suffix;
        suffix *= nums[i];
    }
    return answer;
}

前缀和的应用模式总结

区间和查询： 一维/二维前缀和，O(1) 查询任意区间
子数组计数： 前缀和 + 哈希表，统计满足条件的子数组个数（560）
子数组存在性： 前缀和取模 + 哈希表，判断是否存在满足条件的子数组（523）
前缀积： 乘法版本的"前缀和"，解决乘积类问题（238）

五、差分数组

差分数组是前缀和的逆运算。前缀和擅长查询，而差分数组擅长更新。当我们需要对数组的某个区间频繁进行同一数值的增减操作，并在操作完成后统一查询结果时，差分数组是最优选择。

5.1 定义

对于数组 a[0..n-1]，定义其差分数组 diff[0..n]：

数学定义diff[0] = a[0]
diff[i] = a[i] - a[i-1],  i >= 1

差分数组的前缀和恰好是原数组： a[i] = diff[0] + diff[1] + ... + diff[i]

5.2 区间修改 O(1)

如果要对原数组的区间 [l, r]（含端点）中的每个元素都加上一个值 val，只需要修改差分数组的两个位置：

区间更新操作diff[l] += val;       // 从 l 开始，后续所有元素都加了 val
diff[r + 1] -= val;   // 到 r+1 为止，后面的不再加

这是因为差分数组取前缀和后，diff[l] 的增量会传递到所有 i >= l 的位置，而 diff[r+1] 的减量会在 i >= r+1 处抵消这个增量，最终只有 [l, r] 区间内的元素实际增加了 val。

5.3 单点查询

在完成所有区间更新操作后，原数组 a[i] 可以通过对差分数组求前缀和得到： a[i] = a[i-1] + diff[i]（即累加差分数组）。

5.4 代码模板

C++#include <vector>
using namespace std;

class DifferenceArray {
private:
    vector<int> diff;
    int n;

public:
    // 从原数组构建差分数组 O(n)
    DifferenceArray(vector<int>& nums) {
        n = nums.size();
        diff.resize(n + 1, 0);
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
        // diff[n] = 0 自动初始化，用于处理 r+1 边界
    }

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

    // 执行完所有更新后恢复原数组 O(n)
    vector<int> getResult() {
        vector<int> result(n);
        result[0] = diff[0];
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }
};

Pythonclass DifferenceArray:
    def __init__(self, nums):
        n = len(nums)
        self.diff = [0] * (n + 1)
        self.diff[0] = nums[0]
        for i in range(1, n):
            self.diff[i] = nums[i] - nums[i - 1]
        self.n = n

    def range_add(self, l, r, val):
        self.diff[l] += val
        self.diff[r + 1] -= val

    def get_result(self):
        result = [0] * self.n
        result[0] = self.diff[0]
        for i in range(1, self.n):
            result[i] = result[i - 1] + self.diff[i]
        return result

差分数组的应用场景

多次区间增减后查询： 经典问题如"航班预订统计"（LeetCode 1109）
按差分方式构建数组： 给定一系列增量操作，最终得到整个数组
差分 + 前缀和配合： 先差分处理更新，再前缀和处理查询
扫描线算法： 会议室的可用时间段、区间覆盖问题

典型题目：LeetCode 1109. 航班预订统计

有 n 个航班，编号从 1 到 n。给定 bookings[i] = [first_i, last_i, seats_i] 表示从 first_i 到 last_i 的每个航班都预定了 seats_i 个座位。返回长度为 n 的数组 answer，每个元素是每个航班的总预订数。

解法： 创建差分数组 diff，对每个 booking 执行 diff[first_i-1] += seats_i; diff[last_i] -= seats_i;，最后累加差分数组即可。

六、二维差分

二维差分是将一维差分思想推广到矩阵上，用于实现子矩阵批量更新的高效操作。核心思想与一维完全一致，但更新公式涉及的边界更多。

6.1 子矩阵更新 O(1)

对矩阵中左上角 (r1, c1) 到右下角 (r2, c2) 的子矩阵内所有元素加上 val，需要在差分数组上更新四个位置：

二维差分更新公式diff[r1][c1]     += val;
diff[r1][c2 + 1] -= val;
diff[r2 + 1][c1] -= val;
diff[r2 + 1][c2 + 1] += val;

这里运用了与二维前缀和相同的容斥原理。四个点的修改在经过二维前缀和恢复后，恰好只在 (r1,c1)-(r2,c2) 的子矩阵内生效。

6.2 二维恢复（前缀和）

完成所有子矩阵更新后，通过对差分数组做二维前缀和即可恢复出原矩阵：

恢复公式for i = 1..m:
    for j = 1..n:
        diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]

6.3 代码模板

C++#include <vector>
using namespace std;

class DifferenceArray2D {
private:
    vector<vector<int>> diff;
    int m, n;

public:
    DifferenceArray2D(int rows, int cols) {
        m = rows;
        n = cols;
        // 多开两行两列避免边界检查
        diff.resize(m + 2, vector<int>(n + 2, 0));
    }

    // 子矩阵 (r1,c1) 到 (r2,c2) 加上 val O(1)
    void submatrixAdd(int r1, int c1, int r2, int c2, int val) {
        diff[r1][c1]     += val;
        diff[r1][c2 + 1] -= val;
        diff[r2 + 1][c1] -= val;
        diff[r2 + 1][c2 + 1] += val;
    }

    // 执行二维前缀和，恢复原矩阵 O(m*n)
    vector<vector<int>> getResult() {
        vector<vector<int>> result(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    result[i][j] = diff[i][j];
                } else if (i == 0) {
                    result[i][j] = result[i][j - 1] + diff[i][j];
                } else if (j == 0) {
                    result[i][j] = result[i - 1][j] + diff[i][j];
                } else {
                    result[i][j] = result[i - 1][j] + result[i][j - 1]
                                 - result[i - 1][j - 1] + diff[i][j];
                }
            }
        }
        return result;
    }
};

Pythonclass DifferenceArray2D:
    def __init__(self, rows, cols):
        self.m, self.n = rows, cols
        self.diff = [[0] * (n + 2) for _ in range(m + 2)]

    def submatrix_add(self, r1, c1, r2, c2, val):
        self.diff[r1][c1] += val
        self.diff[r1][c2 + 1] -= val
        self.diff[r2 + 1][c1] -= val
        self.diff[r2 + 1][c2 + 1] += val

    def get_result(self):
        res = [[0] * self.n for _ in range(self.m)]
        for i in range(self.m):
            for j in range(self.n):
                top = res[i - 1][j] if i > 0 else 0
                left = res[i][j - 1] if j > 0 else 0
                diag = res[i - 1][j - 1] if i > 0 and j > 0 else 0
                res[i][j] = top + left - diag + self.diff[i][j]
        return res

七、前缀和 vs 差分对比

前缀和与差分数组是互为"逆运算"的一对技术，下表从多个维度对比它们的异同：

对比维度	前缀和	差分数组
核心目的	优化区间查询（求和）	优化区间更新（批量增减）
数学关系	prefix[i] = sum(a[0..i-1])	diff[i] = a[i] - a[i-1]（以 diff 为前缀和即 a）
与原始数组的关系	prefix 的前缀和 → 原数组的累积	diff 的累积和 → 原数组
构建复杂度	O(n)	O(n)
查询复杂度	O(1) 区间和	O(n) 恢复后才能单点查询
更新复杂度	O(n) 每次更新需重建	O(1) 区间更新
适用场景	查询多、更新少	更新多、查询在更新之后
二维扩展	容斥原理构建 + 四项式查询	四项式更新 + 容斥原理恢复

选择指南

查询密集型（多次查询区间和，极少更新）：选择前缀和
更新密集型（多次区间增减，最后统一查询）：选择差分数组
两者混合：可使用树状数组（Fenwick Tree）或线段树支持动态更新 + 查询
两者结合：差分数组处理更新，前缀和恢复后供查询使用

八、前缀和与哈希表结合优化

前缀和本身只提供原始数组中任意区间的和，要高效解决"寻找满足条件的子数组"这类问题时，需要配合哈希表（Hash Table / HashMap / 字典）来记录前缀和信息。这种结合能将许多 O(n²) 的暴力算法优化到 O(n)。

8.1 两数之和 — 前缀和视角

问题：给定一个整数数组 nums 和一个整数目标值 target，找出和为目标值的两个整数的下标。（LeetCode 1. Two Sum）

前缀和视角： 虽然 Two Sum 并不涉及"子数组和"，但它完美展示了哈希表优化"和等于目标值"的思想。遍历数组时，对每个元素 nums[i]，检查 target - nums[i] 是否已经出现在哈希表中。这与"和为 k 的子数组"问题中的 sum - k 检查完全同构。

C++ LeetCode 1#include <unordered_map>
#include <vector>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (hash.count(complement)) {
            return {hash[complement], i};
        }
        hash[nums[i]] = i;
    }
    return {};
}

8.2 和为 k 的子数组（再探）

这已经在前文 4.1 中详细讨论过。其核心公式是：

核心公式sum(j..i) = prefix[i+1] - prefix[j]
要求 sum(j..i) = k  ⇔  prefix[j] = prefix[i+1] - k
因此：遍历到 i 时，统计之前出现过多少次前缀和为 sum - k

这个模式可以推广到各种变体：求最长子数组长度、求最短子数组长度、统计模 k 余某个值的子数组个数等。

8.3 最长子数组和为 0

问题：给定一个整数数组（可能包含负数），找到和为 0 的最长连续子数组的长度。

解法： 如果两个位置 i、j 的前缀和相等（prefix[i] == prefix[j]），那么子数组 [i..j-1] 的和为 0。用哈希表记录每个前缀和第一次出现的位置，遍历时遇到相同的前缀和就计算距离，取最大值。

C++#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int longestZeroSumSubarray(vector<int>& nums) {
    unordered_map<int, int> hash;
    hash[0] = -1;     // 前缀和为 0 出现在 -1 位置（空前缀）
    int sum = 0, maxLen = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        if (hash.count(sum)) {
            maxLen = max(maxLen, i - hash[sum]);
        } else {
            hash[sum] = i;  // 只记录第一次出现
        }
    }
    return maxLen;
}

8.4 统计优美子数组

问题：给定一个整数数组 nums 和一个整数 k，统计其中恰好包含 k 个奇数的子数组个数。（LeetCode 1248. Count Number of Nice Subarrays）

解法： 将奇数视为 1、偶数视为 0，问题转化为"和为 k 的子数组个数"，直接用 4.1 节的方法解决。

C++ LeetCode 1248#include <unordered_map>
#include <vector>
using namespace std;

int numberOfSubarrays(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    hash[0] = 1;
    int sum = 0, count = 0;
    for (int num : nums) {
        sum += (num & 1);   // 奇数记为 1，偶数记为 0
        if (hash.count(sum - k))
            count += hash[sum - k];
        hash[sum]++;
    }
    return count;
}

哈希表优化模式总结

前缀和 + 哈希表是一个通用模式（也称为"两数之和模式"），适用于以下场景：

统计类： 统计满足 sum(subarray) == k 的子数组个数
存在性类： 判断是否存在满足条件的子数组
最值类： 求最长/最短的满足条件的子数组长度
模运算类： 子数组和能被 k 整除、模 k 余 t 等

所有这类问题的核心公式都是一样的： prefix[i] - prefix[j] == target 等价于 prefix[j] == prefix[i] - target。

九、核心要点总结

前缀和的核心能力： 用 O(n) 预处理换 O(1) 区间和查询，适用于查询多、更新少的场景
差分数组的核心能力： 用 O(1) 区间更新 + O(n) 统一恢复，适用于更新多、查询在最后的场景
互为逆运算： 差分数组的前缀和 = 原数组；原数组的差分 = 差分数组。两者可互相转化
二维扩展： 一维和二维的核心差异在于边界处理——二维需要借助容斥原理处理四个角的加减
哈希表加持： 前缀和 + 哈希表是解决子数组问题的利器，能将 O(n²) 优化到 O(n)
空间换时间： 前缀和和差分数组都是典型的"空间换时间"策略，额外 O(n) 空间换取时间复杂度的质变
进阶方向： 当需要同时支持动态更新和动态查询时，应升级到树状数组（Fenwick Tree）或线段树（Segment Tree）

十、进一步思考

前缀和与差分是数据结构与算法中"预处理"思想的典范。它们的简洁性常让人低估其力量，实际上从区间操作优化的角度看，它们在 many 算法中扮演着基石角色：

扩展应用方向

树上前缀和： 在树结构中，从根节点到任意节点的路径和可以通过 DFS 预计算前缀和实现 O(1) 查询
多维前缀和： 三维及以上空间中的区域和查询，公式随维度增加呈 2^k 项展开
差分约束系统： 差分数组思想是差分约束系统（Difference Constraints）的基础，用于求解不等式组的最短路/最长路问题
离线算法： 差分是 Mo's Algorithm（莫队算法）中重要的离线处理手段
图像处理： 积分图（Integral Image）本质就是二维前缀和，用于快速计算图像中任意矩形区域的像素和