1. 引言在算法竞赛和日常编程中我们常常会遇到需要对数组进行频繁区间操作和快速查询的场景。例如给定一个长度为n的数组需要执行m次“将区间[l, r]内的每个元素都加上c”的操作然后询问某个位置的值。如果直接遍历区间进行修改时间复杂度为O(n*m)在数据量较大时效率极低。差分和前缀和正是为解决这类问题而生的两种高效数据处理技巧。它们通过巧妙的预处理和转换将原本复杂的区间操作和查询问题简化为常数或线性时间的操作是算法工程师和竞赛选手必须掌握的核心工具。2. 前缀和Prefix Sum2.1 基本概念前缀和是一种预处理技术它定义一个新数组s其中s[i]表示原数组a前i个元素的和通常s[0] 0。公式s[i] a[1] a[2] ... a[i]。构建前缀和数组的时间复杂度为O(n)。2.2 核心应用快速区间求和一旦有了前缀和数组计算原数组任意区间[l, r]的和就变得异常简单sum(l, r) s[r] - s[l-1]这样每次区间查询的时间复杂度从O(n)降到了O(1)。2.3 代码示例一维#include iostream #include vector using namespace std; int main() { int n 5; vectorint a {0, 1, 2, 3, 4, 5}; // 下标从1开始a[0]占位 vectorint s(n 1, 0); // 构建前缀和 for (int i 1; i n; i) { s[i] s[i - 1] a[i]; } // 查询区间[2, 4]的和 int l 2, r 4; int sum s[r] - s[l - 1]; // s[4] - s[1] cout Sum of [ l , r ] is: sum endl; // 输出 9 return 0; }2.4 二维前缀和对于二维矩阵前缀和定义为s[i][j]表示从(1,1)到(i,j)的子矩阵元素和。构建公式s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]。查询子矩阵(x1,y1)到(x2,y2)的和sum s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]。3. 差分Difference Array3.1 基本概念差分是前缀和的逆运算。对于一个原数组a其差分数组b定义为b[1] a[1]b[i] a[i] - a[i-1]对于i 1差分数组的核心性质是对原数组a的区间[l, r]同时加上一个常数c等价于对其差分数组b进行两次单点操作b[l] c和b[r1] - c如果r1未越界。3.2 核心应用高效区间修改通过差分我们可以将时间复杂度为O(n)的区间修改操作优化为O(1)的两次单点修改。所有修改完成后通过对差分数组求前缀和即可得到修改后的原数组。3.3 代码示例一维差分#include iostream #include vector using namespace std; int main() { // 原数组假设初始全为0 int n 5; vectorint a(n 2, 0); // 多开一位方便处理 r1 vectorint b(n 2, 0); // 差分数组 // 操作将区间[2, 4]的每个元素加3 int l 2, r 4, c 3; b[l] c; b[r 1] - c; // 操作将区间[1, 3]的每个元素减2 l 1; r 3; c -2; b[l] c; b[r 1] - c; // 通过差分数组前缀和还原修改后的原数组 for (int i 1; i n; i) { b[i] b[i - 1]; // 此时b[i]变成了前缀和即修改后的a[i] a[i] b[i]; cout a[i] ; } // 输出-2 1 1 3 0 return 0; }3.4 二维差分二维差分的思想类似。对子矩阵(x1,y1)到(x2,y2)的所有元素加c等价于对差分矩阵d进行四次单点操作d[x1][y1] c d[x21][y1] - c d[x1][y21] - c d[x21][y21] c最后对d求二维前缀和即可得到修改后的原矩阵。4. 差分与前缀和的结合应用差分和前缀和常常结合使用形成“差分-前缀和”的解题模式区间修改使用差分数组进行高效O(1)修改。状态还原对差分数组求前缀和得到修改后的原数组。区间查询对修改后的数组再求一次前缀和支持O(1)的区间和查询。这种模式将“区间修改区间查询”的复杂度从朴素的O(n*m)优化到O(nm)。5. 典型例题与实战5.1 例题区间加法LeetCode 370问题描述假设你有一个长度为n的数组初始情况下所有的数字均为0。你将会被给出k个更新操作每个操作会被表示为一个三元组[startIndex, endIndex, inc]。你需要将子数组A[startIndex ... endIndex]包括 startIndex 和 endIndex增加inc。请返回k次操作后的数组。差分解法这正是差分的经典应用场景。class Solution { public: vectorint getModifiedArray(int length, vectorvectorint updates) { vectorint diff(length 1, 0); // 差分数组多开一位 for (auto update : updates) { int start update[0], end update[1], inc update[2]; diff[start] inc; if (end 1 length) { diff[end 1] - inc; } } vectorint result(length, 0); result[0] diff[0]; for (int i 1; i length; i) { result[i] result[i - 1] diff[i]; } return result; } };5.2 例题二维区域和检索 - 矩阵不可变LeetCode 304问题描述给定一个二维矩阵计算其子矩形范围内元素的总和。你的sumRegion方法会被多次调用。前缀和解法预处理二维前缀和矩阵每次查询O(1)。6. 总结与对比特性前缀和 (Prefix Sum)差分 (Difference Array)核心思想预处理累加和将区间查询降为O(1)记录相邻元素差值将区间修改降为O(1)主要操作查询区间和区间修改加/减常数时间复杂度构建O(n)查询O(1)修改O(1)还原O(n)空间复杂度O(n)O(n)相互关系差分数组的前缀和是原数组前缀和数组的差分是原数组典型问题静态区间求和、子矩阵求和多次区间修改后单点查询7. 学习建议理解本质差分和前缀和本质上是“空间换时间”和“预处理”思想的体现。掌握推导不要死记硬背公式理解一维和二维情况下的推导过程。勤于练习在 LeetCode、AcWing 等平台寻找相关题目进行实战。联想扩展它们与树状数组、线段树等高级数据结构解决的是同类问题但更简单、高效。掌握差分和前缀和你就能在算法竞赛和面试中轻松应对一大批与区间操作相关的难题。