前缀和--原理详解与常见变式（C/C++ 实现）

前缀和原理详解与常见变式C/C 实现目录基本原理1.1 什么是前缀和1.2 一维前缀和1.3 二维前缀和常见变式2.1 区间和查询2.2 差分数组2.3 环形前缀和2.4 字符串前缀和哈希刷题技巧与模板实战例题总结1. 基本原理1.1 什么是前缀和前缀和Prefix Sum是一种预处理技术通过预先计算累加和来加速区间查询。核心思想将 O(n) 的区间求和查询优化到 O(1)以空间换时间先遍历一次数组构造前缀和数组之后每次查询只需一次减法广泛应用于子数组和、区间计数、矩阵求和等场景1.2 一维前缀和给定数组 arr长度为 n前缀和数组 prefix 定义为prefix[i] arr[0] arr[1] ... arr[i] (0 i n)约定 prefix[-1] 0则任意区间 [l, r] 的和可以表示为sum(l, r) prefix[r] - prefix[l - 1]对于闭区间 [l, r]l r还有一种等价形式sum(l, r) prefix[r 1] - prefix[l] // 常用形式C 实现一维// 标准实现推荐形式vectorintprefix(n1);prefix[0]0;for(inti0;in;i){prefix[i1]prefix[i]arr[i];// prefix[i] arr[0..i-1] 的和}// 查询区间 [l, r]闭区间0-indexedintsumRange(intl,intr){returnprefix[r1]-prefix[l];}1.3 二维前缀和二维前缀和用于矩阵求和场景。设矩阵为 mat行数为 m列数为 nprefix[i][j] mat[0..i-1][0..j-1] 所有元素的和推导公式prefix[i][j] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1] mat[i-1][j-1]C 实现二维vectorvectorintprefix(m1,vectorint(n1,0));for(inti1;im;i){for(intj1;jn;j){prefix[i][j]prefix[i-1][j]prefix[i][j-1]-prefix[i-1][j-1]mat[i-1][j-1];}}// 查询子矩阵 [(x1,y1), (x2,y2)]闭区间intsumMatrix(intx1,inty1,intx2,inty2){returnprefix[x21][y21]-prefix[x1][y21]-prefix[x21][y1]prefix[x1][y1];}2. 常见变式2.1 区间和查询最基础变式适用场景频繁查询固定数组的任意区间和且数组值在查询期间不变。关键点前缀和数组长度 n 1首元素为 0下标对齐更清晰查询时下标 1避免越界判断适用于静态数组数组频繁修改时需用树状数组或线段树2.2 差分数组区间更新 单点查询差分是前缀和的逆运算用于批量区间更新单点查询场景。给定数组 arr差分数组 diff 定义为diff[i] arr[i] - arr[i-1] (i 1) diff[0] arr[0]对区间 [l, r] 执行加 val 操作只需diff[l] val; diff[r 1] - val; // r1 n 时有效否则忽略最后对 diff 做前缀和恢复原数组arr[i] arr[i-1] diff[i]C 实现差分// 构造差分数组vectorintdiff(n1,0);diff[0]arr[0];for(inti1;in;i){diff[i]arr[i]-arr[i-1];}// 区间更新 [l, r] valvoidrangeAdd(intl,intr,intval){diff[l]val;if(r1n)diff[r1]-val;}// 恢复原数组做前缀和for(inti1;in;i){diff[i]diff[i-1];}2.3 环形前缀和处理循环数组当问题涉及环形结构如环形子数组最大和时将数组拼接一份到末尾extended arr arr // 长度翻倍在 extended 上做前缀和然后通过控制窗口大小来模拟环形。C 实现环形vectorintarr2arr;// 复制一份arr2.insert(arr2.end(),arr.begin(),arr.end());// 拼接// 在 arr2 上做前缀和vectorlonglongprefix(n*21,0);for(inti0;in*2;i){prefix[i1]prefix[i]arr2[i];}// 长度为 k 的环形子数组和 prefix[ik] - prefix[i]2.4 字符串前缀和哈希将字符映射为整数用前缀和实现 O(1) 字符串哈希快速判断子串是否相等。常用方法Rabin-Karp 哈希基于进制多项式自然溢出哈希利用 64 位无符号整数溢出C 实现字符串前缀和哈希constlonglongP131;vectorlonglongprefix(n1,0);for(inti0;in;i){prefix[i1]prefix[i]*P(s[i]-a1);}// 哈希值l, r 为闭区间longlonggetHash(intl,intr){returnprefix[r1]-prefix[l]*powP[r-l1];}3. 刷题技巧与模板3.1 何时用前缀和场景适用数据结构复杂度静态区间求和前缀和数组O(n) 预处理O(1) 查询批量区间更新 单点查询差分数组O(1) 更新O(n) 还原批量区间更新 区间查询树状数组 / 线段树O(log n) 更新和查询环形数组问题拼接数组 前缀和O(n) 预处理O(1) 查询3.2 常见错误前缀和数组长度忘 1导致越界区间端点混淆闭区间 vs 左闭右开负数参与取模时未做调整二维前缀和减法忘加回去漏项环形问题窗口大小超过 n 未做限制4. 实战例题例题 1和为 K 的子数组LeetCode 560问题给定整数数组 nums 和整数 k返回和为 k 的连续子数组个数。思路前缀和 哈希表。用哈希表记录每个前缀和出现的次数遍历时检查 (prefix - k) 是否在哈希表中。intsubarraySum(vectorintnums,intk){unordered_mapint,intcnt;cnt[0]1;intprefix0,ans0;for(intnum:nums){prefixnum;anscnt[prefix-k];// 找之前出现多少次 prefix - kcnt[prefix];}returnans;}例题 2二维矩阵求和LeetCode 304问题给定二维矩阵请求子矩阵的元素和支持多次查询。思路二维前缀和预处理。classNumMatrix{vectorvectorintprefix;public:NumMatrix(vectorvectorintmatrix){intmmatrix.size(),nmatrix[0].size();prefix.assign(m1,vectorint(n1,0));for(inti1;im;i){for(intj1;jn;j){prefix[i][j]prefix[i-1][j]prefix[i][j-1]-prefix[i-1][j-1]matrix[i-1][j-1];}}}intsumRegion(intx1,inty1,intx2,inty2){returnprefix[x21][y21]-prefix[x1][y21]-prefix[x21][y1]prefix[x1][y1];}};例题 3航班预订统计LeetCode 1109问题n 个航班预订记录 bookings [i, j, k] 表示从 i 到 j 的航班增加 k 个座位求最终每个航班的座位数。思路差分数组。vectorintcorpFlightBookings(vectorvectorintbookings,intn){vectorintdiff(n1,0);for(autob:bookings){intib[0]-1,jb[1]-1,kb[2];// 转为 0-indexeddiff[i]k;if(j1n)diff[j1]-k;}vectorintans(n);ans[0]diff[0];for(inti1;in;i)ans[i]ans[i-1]diff[i];returnans;}5. 总结前缀和是一种强大的预处理技术核心公式只有两个一维prefix[i1] prefix[i] arr[i]区间和 prefix[r1] - prefix[l]二维prefix[i][j] mat[i-1][j-1] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1]其变式——差分数组、环形扩展、字符串哈希——都是这一思想的延伸。熟练掌握前缀和可以将许多 O(n) 甚至 O(n²) 的题目优化到 O(1) 查询是算法竞赛和面试中的必备技能。