前缀和是一种时间复杂度优化利器尤其适用于频繁查询数组区间和的场景。它通过预先计算“前缀累积和”将原本O(n)时间的区间和查询压缩至O(1)是面试、竞赛及工程开发中高频使用的基础技巧。一、前缀和的原理1.1 定义前缀和Prefix Sum本质是一个辅助数组其中每个元素的值等于原数组从“起始位置”到“当前位置”的所有元素之和。对于一维数组我们通常将前缀和数组定义为pre其数学表达式如下设原数组为a[1...n]注实际开发中常将数组下标从1开始避免处理边界0时的逻辑判断前缀和数组pre[0...n]的定义为pre[0] 0哨兵位用于简化计算pre[i] a[1] a[2] ... a[i]即前i个元素的累积和例如原数组a [1, 2, 3, 4, 5]其前缀和数组pre计算过程如下pre[0] 0哨兵pre[1] a[1] 1pre[2] a[1] a[2] 1 2 3pre[3] a[1] a[2] a[3] 1 2 3 6pre[4] 1 2 3 4 10pre[5] 1 2 3 4 5 15最终pre [0, 1, 3, 6, 10, 15]。1.2 区间和的O(1)查询前缀和的核心作用是快速计算原数组任意区间[l, r]的和。根据前缀和的定义区间和sum(l, r)即a[l] a[l1] ... a[r]可通过前缀和数组推导得出sum(l, r) pre[r] - pre[l-1]推导过程pre[r] a[1] a[2] ... a[l-1] a[l] ... a[r]pre[l-1] a[1] a[2] ... a[l-1]两者相减后前l-1个元素的和被抵消剩余部分恰好是a[l]到a[r]的和。以上述a [1,2,3,4,5]为例若查询区间[2,4]即2349pre[4] 10pre[1] 1sum(2,4) pre[4] - pre[1] 10 - 1 9结果完全正确。1.3 时间与空间复杂度分析前缀和的优势体现在“预处理多次查询”的场景中其复杂度如下预处理阶段遍历原数组一次计算前缀和数组时间复杂度为O(n)n为原数组长度查询阶段每次查询仅需一次减法运算时间复杂度为O(1)无论查询多少次总查询时间仅为O(q)q为查询次数空间复杂度需额外存储长度为n1的前缀和数组空间复杂度为O(n)可优化为原地存储见下文“优化技巧”。对比“暴力查询”每次查询遍历区间[l, r]时间复杂度O(n*q)当查询次数q较大时如q1000前缀和的效率优势会呈指数级放大。二、一维前缀和的C实现一维前缀和是基础其实现流程分为“预处理前缀和数组”和“处理区间查询”两步以下通过完整代码示例讲解。2.1 基础实现下标从1开始下标从1开始是最常用的方式通过pre[0] 0的哨兵位避免处理l1时l-10的边界判断错误。#includeiostream#includevectorusingnamespacestd;intmain(){// 1. 输入原数组长度nintn,q;// n原数组长度q查询次数cinnq;vectorinta(n1);// 原数组a[1]~a[n]for(inti1;in;i){cina[i];}// 2. 预处理前缀和数组prevectorintpre(n1,0);// pre[0] 0pre[1]~pre[n]为前缀和for(inti1;in;i){pre[i]pre[i-1]a[i];// 递推公式当前前缀和 前一个前缀和 原数组当前元素}// 3. 处理q次区间查询while(q--){intl,r;// 查询区间[l, r]cinlr;// 计算区间和并输出intsumpre[r]-pre[l-1];cout区间[l,r]的和为sumendl;}return0;}输入输出示例输入 5 3 // 原数组长度5查询3次 1 2 3 4 5 // 原数组a[1]~a[5] 1 3 // 查询[1,3] 2 4 // 查询[2,4] 3 5 // 查询[3,5] 输出 区间[1,3]的和为6 区间[2,4]的和为9 区间[3,5]的和为122.2 优化技巧原地存储前缀和若原数组后续无需使用可直接在原数组上存储前缀和省去额外的pre数组将空间复杂度从O(n)优化为O(1)不考虑输入数组本身的空间。实现代码如下#includeiostream#includevectorusingnamespacestd;intmain(){intn,q;cinnq;vectorinta(n1);// 原数组与前缀和数组共用for(inti1;in;i){cina[i];a[i]a[i-1];// 原地更新a[i]变为前i个元素的前缀和}while(q--){intl,r;cinlr;couta[r]-a[l-1]endl;}return0;}注意事项此优化仅适用于“原数组无需保留”的场景如仅需查询区间和后续不操作原数组若原数组需后续使用如修改元素后重新计算前缀和则不可使用原地存储。2.3 边界问题处理前缀和的边界错误是新手常见问题需重点关注以下两点下标从0开始的情况若原数组下标从0开始如a[0]~a[n-1]前缀和数组pre[0] 0pre[i] a[0] ... a[i-1]此时区间[l, r]0-based的和为pre[r1] - pre[l]。示例代码如下vectorinta{1,2,3,4,5};intna.size();vectorintpre(n1,0);for(inti1;in;i){pre[i]pre[i-1]a[i-1];// a[i-1]是原数组第i个元素}// 查询区间[1,3]0-based即234intl1,r3;intsumpre[r1]-pre[l];// pre[4]-pre[1] 10-19数据溢出问题若原数组元素为int类型且数值较大如a[i]为1e9n为1e5前缀和可能超过int的最大值2^31-1 ≈ 2e9此时需将前缀和数组类型改为long long。示例vectorlonglongpre(n1,0);// 用long long避免溢出for(inti1;in;i){pre[i]pre[i-1]a[i];// a[i]若为int会自动提升为long long}三、二维前缀和处理矩阵区间和一维前缀和的思想可扩展到二维场景用于快速计算矩阵中任意子矩阵的元素和如查询(x1,y1)到(x2,y2)构成的子矩阵和是图像处理、矩阵分析等领域的常用技巧。3.1 二维前缀和的定义与推导设原矩阵为a[1...n][1...m]下标从1开始二维前缀和数组pre[0...n][0...m]的定义为pre[i][j]表示以(1,1)为左上角、(i,j)为右下角的子矩阵的所有元素之和。递推公式推导要计算pre[i][j]需考虑以下四部分左上角子矩阵(1,1)-(i-1,j-1)的和pre[i-1][j-1]左边子矩阵(1,j)-(i-1,j)的和pre[i-1][j] - pre[i-1][j-1]上边子矩阵(i,1)-(i,j-1)的和pre[i][j-1] - pre[i-1][j-1]当前元素a[i][j]。合并后得到递推公式pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i][j]子矩阵和计算对于任意子矩阵(x1,y1)-(x2,y2)左上角为(x1,y1)右下角为(x2,y2)其和sum的公式为sum pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]推导逻辑用pre[x2][y2]大矩阵和减去“上方无关区域”pre[x1-1][y2]和“左方无关区域”pre[x2][y1-1]但此时“左上角重叠区域”pre[x1-1][y1-1]被多减了一次需加回。3.2 二维前缀和的C实现以下代码实现“输入一个n行m列的矩阵处理q次子矩阵和查询”#includeiostream#includevectorusingnamespacestd;intmain(){intn,m,q;// n行数m列数q查询次数cinnmq;// 1. 输入原矩阵下标1开始vectorvectorinta(n1,vectorint(m1));for(inti1;in;i){for(intj1;jm;j){cina[i][j];}}// 2. 预处理二维前缀和数组vectorvectorlonglongpre(n1,vectorlonglong(m1,0));for(inti1;in;i){for(intj1;jm;j){pre[i][j]pre[i-1][j]pre[i][j-1]-pre[i-1][j-1]a[i][j];}}// 3. 处理q次查询while(q--){intx1,y1,x2,y2;// 子矩阵的左上角(x1,y1)和右下角(x2,y2)cinx1y1x2y2;// 计算子矩阵和longlongsumpre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]pre[x1-1][y1-1];cout子矩阵(x1,y1)-(x2,y2)的和为sumendl;}return0;}输入输出示例输入 3 3 2 // 3行3列矩阵2次查询 1 2 3 // 第1行 4 5 6 // 第2行 7 8 9 // 第3行 1 1 2 2 // 查询子矩阵(1,1)-(2,2)124512 2 3 3 3 // 查询子矩阵(2,3)-(3,3)6915 输出 子矩阵(1,1)-(2,2)的和为12 子矩阵(2,3)-(3,3)的和为15四、前缀和的实战应用场景前缀和并非孤立的技巧而是许多复杂算法的基础组件以下列举典型应用场景。4.1 场景1统计区间和等于k的子数组个数问题描述给定一个整数数组a和整数k统计所有和为k的连续子数组的个数LeetCode 560. Subarray Sum Equals K。前缀和思路设前缀和数组为pre则子数组[i1, j]的和为pre[j] - pre[i]若pre[j] - pre[i] k则pre[i] pre[j] - k遍历数组时用哈希表unordered_map存储每个pre[i]出现的次数对于当前pre[j]查询哈希表中pre[j]-k的出现次数累加至结果。C实现代码#includeiostream#includevector#includeunordered_mapusingnamespacestd;intsubarraySum(vectorintnums,intk){unordered_maplonglong,intpreCount;// key前缀和value出现次数preCount[0]1;// 初始化pre[0] 0出现1次longlongpre0;// 当前前缀和intres0;for(intnum:nums){prenum;// 更新当前前缀和// 若pre - k存在说明有pre[i] pre[j] - k对应子数组和为kif(preCount.find(pre-k)!preCount.end()){respreCount[pre-k];}preCount[pre];// 记录当前前缀和的出现次数}returnres;}intmain(){vectorintnums{1,1,1};intk2;cout和为k的子数组个数subarraySum(nums,k)endl;// 输出2return0;}复杂度分析时间复杂度O(n)遍历数组一次哈希表查询/插入为O(1)空间复杂度O(n)哈希表存储前缀和。4.2 场景2二维矩阵中的最大子矩阵和问题描述给定一个二维整数矩阵找到一个子矩阵使其元素和最大类似“二维版最大子数组和”。前缀和思路用二维前缀和预处理矩阵将任意子矩阵和的计算降为O(1)固定子矩阵的“上下边界”如固定第i行到第j行将每列的和压缩为一个“一维数组”列和数组对列和数组求“最大子数组和”Kadane算法即为“上下边界为i~j”时的最大子矩阵和遍历所有可能的上下边界取最大值即为最终结果。核心优势将二维问题转化为一维问题时间复杂度从O(n^2m^2)暴力枚举所有子矩阵优化为O(n^2m)n为行数m为列数。4.3 场景3前缀和与差分的结合前缀和与差分是“逆运算”关系差分数组的前缀和是原数组原数组的前缀和是“二次前缀和”。两者结合可高效解决“多次区间更新区间查询”的问题如LeetCode 1109. Corporate Flight Bookings。例如若需对数组a的[l, r]区间每次加val共q次更新最后查询[x, y]的和用差分数组diff处理区间更新diff[l] valdiff[r1] - val更新时间O(1)对diff求前缀和得到更新后的a数组时间O(n)对a求前缀和查询[x, y]的和时间O(1)。总时间复杂度O(n q)远优于暴力更新的O(q*n)。五、总结5.1 前缀和的核心优势时间优化将多次区间和查询的时间从O(n*q)降至O(n q)是“以空间换时间”的经典案例通用性强可扩展到二维、三维场景且能与哈希表、Kadane算法等结合解决复杂问题实现简单核心逻辑仅需几行代码易于理解和调试。5.2 常见误区与避坑指南下标混淆务必明确原数组和前缀和数组的下标起始位置0-based或1-based避免查询时出现l-1越界数据溢出当原数组元素较大或长度较长时前缀和需用long long类型尤其二维前缀和矩阵元素和更容易溢出空间浪费若原数组无需保留可使用“原地前缀和”优化空间不适用于动态修改前缀和仅适用于“静态数组”元素不修改若需频繁修改元素并查询区间和应使用线段树或树状数组。