🧠 算法学习日记 | 今天我用「前缀和」解了两道题，原来“预处理”能这么强！
大家好，我是你们的算法学习搭子 👋
今天继续我的算法入门之旅，重点练习了**前缀和（Prefix Sum）**这一高效的数据预处理技巧。
很多人觉得“前缀和”只是用来快速求区间和的工具，但其实，它是一种通过空间换时间的典型思想。
只要我们提前把信息存好，就能在 $ O(1) $ 时间内回答任意查询。
今天我完整做了两道题，每一道都坚持用最朴素的前缀和逻辑实现。下面我把题目原文和我的原始代码原封不动贴出来，不做任何删减或美化，只为真实记录学习过程。
🔹 题目一：区间次方和
问题描述
给定一个长度为 $ n $ 的整数数组 $ a $ 以及 $ m $ 个查询。
每个查询包含三个整数 $ l, r, k $，表示询问 $ l \sim r $ 之间所有元素的 $ k $ 次方和。
请对每个查询输出一个答案，答案对 $ 10^9 + 7 $ 取模。
输入格式
第一行输入两个整数 $ n, m $，其含义如上所述。
第二行输入 $ n $ 个整数 $ a[1], a[2], \ldots, a[n] $。
接下来 $ m $ 行，每行输入三个整数 $ l, r, k $，表示一个查询。
输出格式
输出 $ m $ 行，每行一个整数，表示查询的答案对 $ 10^9 + 7 $ 取模的结果。
样例输入
5 3 1 2 3 4 5 1 3 2 2 4 3 3 5 1样例输出
14 99 12评测数据规模
对于 100% 的评测数据：$ 1 \leq n, m \leq 10^5，，，1 \leq a[i] \leq 100，，，1 \leq l \leq r \leq n，，，1 \leq k \leq 5 $。
✅ 我的代码
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constll N=1e5+9;ll a[6][N],prefix[6][N];constll p=1e9+7;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intn,m;intl,r,k;cin>>n>>m;for(inti=1;i<=n;++i)cin>>a[1][i];for(inti=2;i<=5;++i){for(intj=1;j<=n;++j){a[i][j]=(a[i-1][j]*a[1][j])%p;}}for(inti=1;i<=5;++i){for(intj=1;j<=n;++j){prefix[i][j]=(prefix[i][j-1]+a[i][j])%p;}}for(inti=0;i<m;++i){cin>>l>>r>>k;cout<<((prefix[k][r]-prefix[k][l-1]+p)%p)<<endl;}return0;}🔹 题目二：小郑的蓝桥平衡串
问题描述
平衡串指的是一个字符串，其中包含两种不同字符，并且这两种字符的数量相等。
例如，ababab和aababb都是平衡串，因为每种字符各有三个，而abaab和aaaab都不是平衡串，因为它们的字符数量不相等。
平衡串在密码学和计算机科学中具有重要应用，比如可以用于构造哈希函数或者解决一些数学问题。
小郑拿到一个只包含 $ L、、、Q $ 的字符串，他的任务就是找到最长平衡串，且满足平衡串的要求，即保证子串中 $ L、、、Q $ 的数量相等。
输入格式
输入一行字符串，保证字符串中只包含字符 $ L、、、Q $。
输出格式
输出一个整数，为输入字符串中最长平衡串的长度。
样例输入
LQLL样例输出
2评测数据规模
对于所有评测数据，输入字符串的长度 $ len \leq 1000 $。
✅ 我的代码
#include<bits/stdc++.h>usingnamespacestd;constintN=1010;intprefix[N];intmain(){string s;cin>>s;intn=s.length();prefix[0]=0;for(inti=0;i<n;++i){if(s[i]=='L'){prefix[i+1]=prefix[i]+1;}else{prefix[i+1]=prefix[i]-1;}}intans=0;for(intl=0;l<=n;++l){for(intr=l+1;r<=n;++r){if(prefix[r]==prefix[l]){intlen=r-l;if(len>ans)ans=len;}}}cout<<ans;return0;}🌟 我的思考
这两道题虽然看起来完全不同，但都用了前缀和的思想：
- 区间次方和：先预处理出每个幂次的前缀和，再用 $ \text{sum}[r] - \text{sum}[l-1] $ 快速回答查询。
- 平衡串：用
prefix[i]表示从开头到第 $ i $ 位，L和Q的差值。当两个位置的prefix值相等时，说明中间子串是平衡的。
你会发现：
前缀和的本质是“信息压缩”—— 把一段区间的统计信息，压缩成一个数值，方便后续快速查询。
而且，前缀和不仅能处理“和”，还能处理“差”、“出现次数”、“奇偶性”等抽象状态。
比如在平衡串中，我们并不关心具体有多少个L或Q，只关心它们的相对数量差。这个差值的变化可以用前缀和来追踪。
✅ 总结
- 前缀和的核心是：预处理 + 快速查询
- 适用于多次查询同一数组区间的问题
- 可以扩展到二维、多维、非数值型（如字符计数）
- 关键在于定义合适的“前缀值”（如和、差、次数等）
- 时间复杂度：预处理 $ O(n) $，每次查询 $ O(1) $
如果你也在刷算法题，不妨试试今天这三道题，用最直白的前缀和方法做一遍。
有时候，简单的预处理，也能带来巨大的效率提升。
欢迎在评论区贴出你的解法，我们一起交流进步！👇
