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

前缀和

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

目录

1. 基本原理
   • 1.1 什么是前缀和
   • 1.2 一维前缀和
   • 1.3 二维前缀和
2. 常见变式
   • 2.1 区间和查询
   • 2.2 差分数组
   • 2.3 环形前缀和
   • 2.4 字符串前缀和（哈希）
3. 刷题技巧与模板
4. 实战例题
5. 总结

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++ 实现（一维）

// 标准实现（推荐形式）vector<int>prefix(n+1);prefix[0]=0;for(inti=0;i<n;i++){prefix[i+1]=prefix[i]+arr[i];// prefix[i] = arr[0..i-1] 的和}// 查询区间 [l, r]（闭区间，0-indexed）intsumRange(intl,intr){returnprefix[r+1]-prefix[l];}

1.3 二维前缀和

二维前缀和用于矩阵求和场景。设矩阵为 mat，行数为 m，列数为 n：

prefix[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++ 实现（二维）

vector<vector<int>>prefix(m+1,vector<int>(n+1,0));for(inti=1;i<=m;i++){for(intj=1;j<=n;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[x2+1][y2+1]-prefix[x1][y2+1]-prefix[x2+1][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; // r+1 < n 时有效，否则忽略

最后对 diff 做前缀和恢复原数组：

arr[i] = arr[i-1] + diff[i]

C++ 实现（差分）

// 构造差分数组vector<int>diff(n+1,0);diff[0]=arr[0];for(inti=1;i<n;i++){diff[i]=arr[i]-arr[i-1];}// 区间更新 [l, r] += valvoidrangeAdd(intl,intr,intval){diff[l]+=val;if(r+1<n)diff[r+1]-=val;}// 恢复原数组（做前缀和）for(inti=1;i<n;i++){diff[i]+=diff[i-1];}

2.3 环形前缀和（处理循环数组）

当问题涉及"环形结构"（如环形子数组最大和）时，将数组拼接一份到末尾：

extended = arr + arr // 长度翻倍

在 extended 上做前缀和，然后通过控制窗口大小来模拟环形。

C++ 实现（环形）

vector<int>arr2=arr;// 复制一份arr2.insert(arr2.end(),arr.begin(),arr.end());// 拼接// 在 arr2 上做前缀和vector<longlong>prefix(n*2+1,0);for(inti=0;i<n*2;i++){prefix[i+1]=prefix[i]+arr2[i];}// 长度为 k 的环形子数组和 = prefix[i+k] - prefix[i]

2.4 字符串前缀和（哈希）

将字符映射为整数，用前缀和实现 O(1) 字符串哈希，快速判断子串是否相等。

常用方法：

• Rabin-Karp 哈希：基于进制多项式
• 自然溢出哈希：利用 64 位无符号整数溢出

C++ 实现（字符串前缀和哈希）

constlonglongP=131;vector<longlong>prefix(n+1,0);for(inti=0;i<n;i++){prefix[i+1]=prefix[i]*P+(s[i]-'a'+1);}// 哈希值（l, r 为闭区间）longlonggetHash(intl,intr){returnprefix[r+1]-prefix[l]*powP[r-l+1];}

3. 刷题技巧与模板

3.1 何时用前缀和

3.2 常见错误

• 前缀和数组长度忘 +1，导致越界
• 区间端点混淆（闭区间 vs 左闭右开）
• 负数参与取模时未做调整
• 二维前缀和减法忘加回去漏项
• 环形问题窗口大小超过 n 未做限制

4. 实战例题

例题 1：和为 K 的子数组（LeetCode 560）

问题：给定整数数组 nums 和整数 k，返回和为 k 的连续子数组个数。

思路：前缀和 + 哈希表。用哈希表记录每个前缀和出现的次数，遍历时检查 (prefix - k) 是否在哈希表中。

intsubarraySum(vector<int>&nums,intk){unordered_map<int,int>cnt;cnt[0]=1;intprefix=0,ans=0;for(intnum:nums){prefix+=num;ans+=cnt[prefix-k];// 找之前出现多少次 prefix - kcnt[prefix]++;}returnans;}

例题 2：二维矩阵求和（LeetCode 304）

问题：给定二维矩阵，请求子矩阵的元素和，支持多次查询。

思路：二维前缀和预处理。

classNumMatrix{vector<vector<int>>prefix;public:NumMatrix(vector<vector<int>>&matrix){intm=matrix.size(),n=matrix[0].size();prefix.assign(m+1,vector<int>(n+1,0));for(inti=1;i<=m;i++){for(intj=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];}}}intsumRegion(intx1,inty1,intx2,inty2){returnprefix[x2+1][y2+1]-prefix[x1][y2+1]-prefix[x2+1][y1]+prefix[x1][y1];}};

例题 3：航班预订统计（LeetCode 1109）

问题：n 个航班，预订记录 bookings = [i, j, k] 表示从 i 到 j 的航班增加 k 个座位，求最终每个航班的座位数。

思路：差分数组。

vector<int>corpFlightBookings(vector<vector<int>>&bookings,intn){vector<int>diff(n+1,0);for(auto&b:bookings){inti=b[0]-1,j=b[1]-1,k=b[2];// 转为 0-indexeddiff[i]+=k;if(j+1<n)diff[j+1]-=k;}vector<int>ans(n);ans[0]=diff[0];for(inti=1;i<n;i++)ans[i]=ans[i-1]+diff[i];returnans;}

5. 总结

前缀和是一种强大的预处理技术，核心公式只有两个：

• 一维：prefix[i+1] = prefix[i] + arr[i]，区间和 =prefix[r+1] - 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) 查询，是算法竞赛和面试中的必备技能。