【算法思想】前缀和

引入

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。 观察上面的要求，输入一个长度为n的整数序列，根据输入的询问，输出从第l个数到第r个数的和。 如果遍历后一个一个加，在数据很大的情况下，会超时。 那么怎么做才可以简化代码呢？ ——用前缀和

基本介绍

前缀和，这三个字，顾名思义表示是一个和，并且是某段序列的前缀的和。 我们回到上一个题，如果我们提前知道第1个数到l-1个数的和，还有第1个数到第r个数的和，那么它们相减是不是可以直接得出结果，这个时间复杂度就是O(N)了； 那么如何得出从第一个数到某个数的和呢？（也就是前缀和的具体做法） 先定义一个数组s[N],s[i]表示从第一个数字到第i个数字的和。 我们输入一段长度为n的序列，如果是一个个输入的，那么每输入一个就加到s[i]上，并且s[i]还需要加上s[i-1] 则代码为： s[0]=0; for(int i=1;i<=n;i++) { cin»a[i]; s[i]=a[i]+s[i-1]; } ⭐前缀和有个很重要的部分： 由于s[i]需要去加上s[i-1]。为了使数组不访问到未知区域，所以s[i]中的i都需要从1开始，如果输入的a[i]输入必须要从0开始，那么代码就需要变成s[i+1]=a[i]+s[i] 🆗 现在基本了解了前缀和的思路，那么先做个例题来写一下吧

例题1

题目描述：

分析1

在题目中可看出来，它要求计算Ai到Aj的和是否是K倍的， 那根据上面介绍的前缀和思想，我们很容易能想出做题方法。 首先定义两个数组长度为N的最大值（100010）多一个10，这样比较保险。 一个数组是用于存储长度为n的数组a[N]，一个存储前缀和s[N]. ⭐注意，我们定义完后，需要明晰前缀和数组s[i]表示的是什么意思——s[i]表示从1开始到第i个元素的总和。 求出s[i]数组后，我们现在需要解决输出问题——我们需要输出区间内的和为K倍的区间数量。 很容易的能想到for循环嵌套，去一一遍历，但由于数据范围是10的5次方，n的平方的时间复杂度显然是过不去的。所以需要另寻方法 这里引入一个数学上的（同余原理）

同余原理

如果想让（s[i]-s[j-1]被k整除，等同于，s[i]取余k等于s[j-1]取余k。 那么为了方便，我们在输入a[i]数组，给s[i]赋值的同时，直接取余k， 那这时候可能会有人疑惑了，取余k之后，去判断前缀和数组的两个数是否相等不还是需要两个for循环嵌套吗？ 这里就需要借用另一个数组来实现了，我们定义一个st[N]数组， 它表示 s数组中取余k后结果相同的 数量 表示形式为——st[s[i]]，这个就可以表示与s[i]取余k相等的数量 ⭐注意，1个数也可以当数组，所以不用去掉s[i]本身的数量 而取余0也就是st[0]表示：前缀和取模后余数为 0 的次数。每个余数为 0 的前缀和本身对应一个 从起点到当前位置的区间 ，这些区间的和本身就是 K 的倍数。 而且st[s[i]]，它最终要算的次数是从这个结果里面，拿出两个数作为区间端点，也就是C(m,2)，从m个数任意挑选两个数字，表示为：(st[i]*(st[i]-1))/2 分析完了，现在可以写出代码了。

代码1

#include #include #include using namespace std; #define N 100010 long long s[N],st[N]; int a; int flag; int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a); s[i]=(s[i-1]+a)%k; st[s[i]]++; } long long res=st[0]; for(int i=0;i * 虚拟前缀和：引入一个不存在的 s[0] = 0（对应空数组的和）。

• 作用：当某个实际前缀和 s[i] ≡ 0 (mod K) 时，区间 [1, i] 的和自动满足 s[i] - s[0] ≡ 0 (mod K)，即该区间有效。
• 示例：若 A = [3]，K = 3，则 s[1] = 0，此时 s[1] - s[0] = 0，区间 [1,1] 有效。
• 避免漏算：如果没有这个虚拟的 s[0]，当 s[i] ≡ 0 时，无法统计从数组开头到 i 的区间。

2 遍历时实时统计的逻辑

• 操作步骤： 对每个 i（从 1 到 N）：

1. 计算 s[i] = (s[i-1] + A[i]) % K。
2. 立即将 cnt[s[i]] 累加到结果：

• 当前 s[i] 的余数为 r，之前所有余数为 r 的前缀和（即 cnt[r] 次）均可与当前 s[i] 形成有效区间。 3 再更新 cnt[s[i]]：将当前余数 r 的计数加 1，供后续前缀和匹配。

• 动态维护的直观解释：

• 统计的是历史匹配次数：每次处理 s[i] 时，cnt[r] 表示在 i 之前，余数为 r 的前缀和已经出现的次数。

• 组合数的实时计算：每个新余数 r 贡献 cnt[r] 个新区间，最终所有余数 r 的总贡献为 Σ cnt[r] * (cnt[r]-1)/2（但通过动态累加避免了显式计算组合数）。

假如s[1]是1，而s[2]也是1，第一次的时候由于s[1]无法和别人组成区间，所以res+=0;而当到s[2]时，由于此时cnt[1]加加过了，所以为1，res+=1;表示1，2组成一个区间。 也就是位置2到位置2的和属于是K倍区间的情况。

代码2：

#include #include #include using namespace std; #define N 100010 long long s[N],st[N]; int a; int flag; int main() { int n,k; scanf("%d%d",&n,&k); st[0]=1;//这样从头开始到第i个位置的这种情况就不会被漏掉。 //它表示s[i]=0，也就是这个和本身就是K倍。 for(int i=1;i<=n;i++) { scanf("%d",&a); s[i]=(s[i-1]+a)%k; res+=st[s[i]]; st[s[i]]++; } cout< #include #include using namespace std; const int N=10e5+10; int a[N],b[N],c[N]; int n; int main() { scanf("%d",&n); for(int i=0;i>1; if(a[mid]>1; if(c[mid]<=b[i])l=mid; else r=mid; }int q=n-l-1; res+=(long long)p*q; //cout< #include #include using namespace std; const int N=10e5+10; int a[N],b[N],c[N]; int n; long long cnt1[N],cnt2[N]; long long s1[N],s2[N]; void sr(int *p,long long *cnt) { for(int i=0;i> x » y » w; x++; y++; // 将坐标转换为1-based索引 g[x][y] += w; // 累加同一位置的价值

• 原题坐标范围是05000 → 转换为15001，避免处理负数索引

2 计算前缀和

for(int i=1; i<=a; i++) for(int j=1; j<=b; j++) s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];

• 这里s数组既存储原始价值，又存储前缀和（节省内存）

3 遍历所有可能的正方形

for(int i=r; i<=a; i++) for(int j=r; j<=b; j++) res = max(res, s[i][j] - s[i-r][j] - s[i][j-r] + s[i-r][j-r]);

• 枚举正方形的右下角坐标(i,j)
• 通过前缀和公式快速计算区域和

代码：

#include #include #include using namespace std; const int N=5010; int a,b; int s[N][N];//原数组，后面可以变成二维数组存储前缀和 int main() { int n,r; cin»n»r; r=min(5001,r); a=b=r; while(n–) { int x,y,w; cin»x»y»w; x++; y++; a=max(a,x); b=max(b,y); s[x][y]+=w; } for(int i=1;i<=a;i++) { for(int j=1;j<=b;j++) { s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; //cout«s[i][j]«endl; } } int res=0; //枚举它,从右下角枚举所以初始坐标为r for (int i = r; i <= a; i ++ ){ for (int j = r; j <= b; j ++ ){ res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]); } } cout«res«endl; return 0; }

总结

前缀和思想是一种通过预处理数组来高效计算区间和的算法技巧，其核心在于通过预计算并存储前n项的和，将原本复杂的区间查询问题转化为简单的差值运算，从而大幅优化时间复杂度。以下是其详细用法总结：

一、核心思想

1. 预处理 数组：构建前缀和数组 sum，其中 sum[i] 表示原数组前i项的和。例如，原数组 a[1...n] 的前缀和数组满足 sum[i] = sum[i-1] + a[i]，从而快速计算任意区间 [l, r] 的和为 sum[r] - sum[l-1] 。
2. 优化 时间复杂度：将暴力法的O(n²)或O(n³)复杂度降至O(n)预处理 + O(1)查询，适用于多次区间和查询的场景 。

二、典型应用场景

1. 一维数组问题 ：

• 寻找中心索引 ：通过比较左侧前缀和与右侧（总和 - 左侧 - 当前元素）是否相等，快速定位中心索引 。
• 和为K的子数组 ：利用哈希表记录前缀和出现的次数，统计满足 sum[j] - sum[i] = K 的子数组数量，将时间复杂度从O(n²)优化至O(n) 。
• 统计特定条件的子数组 ：如优美子数组（含k个奇数）、和可被K整除的子数组，结合哈希表记录前缀奇数的数量或余数分布，实现高效统计 。

2. 二维矩阵问题 ：

• 子矩阵和计算 ：构建二维前缀和矩阵 s[i][j]，通过公式 s[i][j] = prefixSum[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j] 预处理，查询时用容斥原理计算子矩阵和 。

三、一些小tips

1. 结合哈希表 ：在统计满足特定条件的子数组时，哈希表可存储前缀和（或余数、奇数个数等）的频率，避免双重循环遍历。例如，哈希表初始化需包含 hash[0] = 1，以处理前缀和直接等于目标值的情况 。
2. 负数处理 ：当涉及余数计算（如和可被K整除）时，需将负数余数调整为正值。例如，(sum % K + K) % K 确保余数在 [0, K-1] 范围内 。
3. 空间优化 ：无需显式构建前缀和数组时，可直接用变量累加前缀和，减少空间占用 。
4. 扩展应用 ：前缀和思想可推广至其他运算（如异或、乘积）或变种问题（如前缀GCD、差分数组），例如统计区间异或结果或动态数组修改后的区间和 。

四、代码实现要点

• 一维前缀和模板 ： for (int i=1; i<=n; ++i) { sum[i] = sum[i-1] + arr[i]; } // 查询区间[l, r]的和：sum[r] - sum[l-1]
• 二维前缀和模板 ： for (int i=1; i<=n; ++i) { for (int j=1; j<=m; ++j) { s[i][j] = s[i-1][j] + s[i][j-1]

• s[i-1][j-1] + a[i][j]; } }

五、最后总结

前缀和思想——关键在于灵活运用预处理数据与哈希映射 ，同时注意边界条件与负数处理，可以用在不同的算法题场景中。