目录1. 前缀和原理与特点2. 实现前缀和3. 例题3.1区间次方和3.2小郑的蓝桥平衡串在算法竞赛如蓝桥杯中如果在处理海量数据时遇到了频繁查询“某一段区间数据总和”的需求如果每次查询都用 for 循环从头加到尾程序肯定会因为超时TLE而痛失分数。为了解决这个问题算法竞赛中引入了一个极其优雅且高效的技巧——前缀和Prefix Sum。今天我们就来深入拆解前缀和的原理并结合两道蓝桥杯真题进行实战演练。1. 前缀和原理与特点前缀和prefix顾名思义就是从数组开头一直累加到当前位置的“前面所有元素的总和”。简单来说前缀和数组是由用户输入的基础数组生成的一个辅助数组。假设我们有一个原数组 a那么它的前缀和数组 prefix 中第 i 个元素prefix[i]就代表了原数组中a[1]到a[i]的所有元素之和。前缀和最大的特点与核心价值在于用空间换时间。通过在读取数据时额外花一点点时间线性时间预处理出一个前缀和数组我们在后续面对成千上万次“求某个区间总和”的查询时就可以把查询时间瞬间从线性级别降维打击到常数级别也就是瞬间得出结果。2. 实现前缀和实现前缀和通常分为两步预处理和区间查询。为了防止在计算prefix[i - 1]时出现数组下标越界比如下标变成 -1我们在算法竞赛中通常习惯将数组下标从 1 开始使用并且默认prefix[0] 0。预处理构建前缀和数组for(int i 1; i n; i) prefix[i] prefix[i - 1] a[i];在这个循环中当前位置的前缀和就等于“前一个位置的前缀和”加上“当前位置的元素值”。这种递推方式非常高效。求区间和假设我们要查询原数组中从第 L 个元素到第 R 个元素包含 L 和 R的总和我们只需要用一个简单的减法公式sum(L, R) prefix[R] - prefix[L - 1];3. 例题下面我们结合两道蓝桥杯真题来看看前缀和算法在实战中是如何大显身手的。3.1区间次方和https://www.lanqiao.cn/problems/3382/learning/?page1first_category_id1problem_id3382思路解析这道题不仅要求我们求区间和还要求我们求区间的“k次方”和k的值在1到5之间。同时因为结果可能非常大题目要求对 10的9次方加7 取模。既然 k 只有 1 到 5 这五种可能我们完全可以定义一个二维的前缀和数组prefix[6][N]分别存储 1 次方、2 次方、一直到 5 次方的前缀和。另外代码中包含两个非常关键的细节快速求幂pow_k函数利用位运算的思想快速求出 base 的 exp 次方并取模效率远超普通的 for 循环相乘。处理取模时的负数在 C 中两个正数取模后的结果相减可能会产生负数比如 3 - 5 -2。为了保证结果恒为正且符合取模规则区间求和的公式要写成(prefix[k][r] - prefix[k][l - 1] p) % p也就是先加上模数 p 再取模。参考代码#include bits/stdc.h using namespace std; using ll long long; ll p 1e9 7; const int N 1e5 10; int a[N]; ll prefix[6][N]; // 自定义求幂函数计算 (base^exp) % p ll pow_k(ll base, int exp) { ll res 1; base base % p; // 防止底数过大虽然本题 a[i] 100 不会越界但加上更严谨 while (exp 0) { if (exp % 2 1) res (res * base) % p; // 如果指数当前位是1累乘到结果中 base (base * base) % p; // 底数平方 exp / 2; // 指数右移 } return res; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin n m; for(int i 1; i n; i) cin a[i]; // 前缀和数组 for(int k 1; k 5; k) { prefix[k][0] 0; for(int i 1; i n; i) { // 前i个的和 前i-1个的和 当前元素的k次方取模 prefix[k][i] (prefix[k][i - 1] pow_k(a[i], k)) % p; } } // 处理每个查询 while(m--) { int l, r, k; cin l r k; // 求区间和 ll ans (prefix[k][r] - prefix[k][l - 1] p) % p; cout ans \n; } return 0; }3.2小郑的蓝桥平衡串https://www.lanqiao.cn/problems/3419/learning/?page1first_category_id1problem_id3419思路解析题目要求寻找最长的平衡子串所谓平衡串就是字符串中两种特定字符的数量相等。 这里用到了一种非常经典的“前缀和变体”技巧把其中一种字符例如 L看作 1把其他字符看作 -1。这样一来如果某一个区间 [i1, j] 是平衡串就意味着这个区间里的 1 和 -1 数量相等也就是这个区间的和为 0。 根据前缀和公式区间和 prefix[j] - prefix[i]。 既然区间和等于 0那么就推导出prefix[j] prefix[i]。因此这道题的本质就变成了在 prefix 数组中寻找两个值相同且距离最远的下标 i 和 j。代码中通过嵌套的两层循环遍历所有的起点和终点找出了跨度最大的那对相等的前缀和。参考代码#include bits/stdc.h using namespace std; const int N 1010; char s[N]; int prefix[N]; int main() { cin s 1; int len strlen(s 1); for(int i 1; i len; i) prefix[i] prefix[i - 1] (s[i] L ? 1 : -1); int ans 0; for(int i 0; i len; i) { for(int j i 1; j len; j) { if(prefix[i] prefix[j]) { ans max(ans, j - i); } } } cout ans \n; return 0; }本章完。