打开牛客网刷题记录我翻到自己存的第二份刷题笔记里面正好有一道题让我卡了整整一下午就是那道“区间次方和”。当时做完之后我专门把整个思路演变过程、踩过的坑、换过的解法都记了下来今天整理出来分享给正在准备春招秋招、或者单纯想练算法思维的朋友。如果你是第一次听到这种题型也不用慌我会从最暴力的写法一路讲到最优解尽量把每一步为什么这么做讲清楚。这道题其实特别典型它表面上是区间查询问题实际上考的是数学化简加预处理思维很多人在牛客上遇到它时第一反应是用线段树结果反而把自己绕晕了。我整理这份记录的目的就是帮你把这层窗户纸捅破看完之后你不仅能拿下这一道题以后遇到类似的“区间操作型”题目心里也会有个判断框架。1. 为什么我选了这道题高频但容易被带偏的区间处理题目1.1 第一印象看着像数据结构题其实不是先说下题目长什么样。给定一个长度为n的数组以及m次查询每次查询给三个数l、r、k要求你算出数组里从下标l到r这连续一段每个数的k次方加在一起的结果输出时要对某个模数取模常见是1e97。我第一次看到这个题的时候脑子里冒出来的第一个想法是“这不是线段树吗”毕竟区间求和、区间修改这类操作线段树是标配。但仔细一看不对劲因为K次方这个东西它没法像加法那样维护——你想用线段树维护区间和关键在于父节点的信息能用子节点直接合并出来比如sum left.sum right.sum。但次方和就不一样了left区间的a^k加right区间的b^k你没有任何办法从它们的次方和里推出整个区间的(ab)^k之类的结果除非你提前把所有k的情况都存下来。所以这道题选线段树从一开始就方向错了。1.2 考点拆解前缀和思维、快速幂、取模运算三合一真正解这道题需要的其实是三块基础能力的组合。一是前缀和思想但这个前缀和不是我一开始以为的那种直接对原数组求前缀和而是要对“每个值出现了多少次”做前缀和。二是快速幂因为你真的需要对一个数算它的k次方k最大能到1e9甚至更大直接循环乘肯定超时必须用快速幂把单次幂运算压到log级别。三是取模运算的严谨性加减乘都要随时取模尤其减法取模要防负数这个我后面单独讲坑。这三个考点单拎出来都不算难但放在一道题里就会筛掉一大批人。牛客上这道题的通过率我记得不算高不是因为题目有多难而是因为它太容易让你走弯路一旦开始想复杂了就不容易回头。1.3 适合谁看这份记录如果你正在刷牛客的算法题库尤其是冲着大厂笔试面试去的这道题值得花两个小时认真弄懂。因为它考察的并不是什么冷门偏怪的知识点恰恰是在实际笔试里出现频率很高的几样东西的组合。如果你刚开始刷题不久线段树这些还没学透也没关系看完这一篇你会发现这道题根本不需要线段树反而对新手更友好。2. 思路演进从暴力解法到正解的完整推导过程2.1 暴力解法第一步永远是能算出正确答案做题第一步一定不要好高骛远先把最朴素、最不可能错的写法搞出来哪怕它超时。暴力做法就是对每一次查询从l到r遍历一遍每个元素算一遍k次方累加。假设n是1e5m是1e5k本身也要参与计算。如果每次查询区间长度平均是n/2那光遍历数组就是5e9次操作再算上幂运算内部还要乘k次这时间复杂度已经离谱到没法看了大概是O(m乘以n乘以k)的天文数字。可以这样说数据但凡稍微给大一点暴力写法连运行结束的机会都没有。但暴力解法的意义在于验证你的思路。我自己在本地测试的时候会先写一个暴力版本专门用来对比优化版代码的输出结果确保优化版本在逻辑上没有改错。这个习惯强烈建议你保留别上来就写正解万一正解写歪了你都找不到参照物。2.2 前缀和的疑云为什么不能直接预处理所有k次方接下来自然的想法是区间查询嘛我预处理一个前缀和数组prefix[i]表示前i项的k次方和那查询就是prefix[r]减prefix[l-1]O(1)搞定。问题来了——k是每次查询的时候给的不是一个固定的数。你第一次查询k2第二次可能k5第三次k可能等于1e9。你要预处理所有k的情况就得准备一个二维数组行是每个下标列是每个可能的k这个空间复杂度是n乘以k的范围也就是1e5乘以1e9直接爆内存到妈都不认识。那你说我压缩一下只处理查询中出现过的k这也是一种补救思路把查询离线化去重之后只对用到的k分别建前缀和。但把数组长度乘去重后的k数量最坏情况下仍然是1e5乘1e51e10级别的空间还是不行。所以关键矛盾在于k是动态的而前缀和是静态的两者没法直接匹配。你得换个角度不是对数组位置做前缀和而是对“数值种类”做文章。2.3 正解灵魂把“求区间和”变成“统计值出现次数”这里就要看看题目有没有额外的条件。通常牛客上这题会给一个不太显眼的限制数组元素a[i]的值域不会太大。有的版本明确写a[i]不超过100有的版本比较阴不写在题干里但数据范围那一栏写了a[i]小于等于某个小数字。这个条件才是整道题真正的突破口。想明白这一点思路就彻底变了。对于一次查询l、r、k区间里的数虽然很多但种类数是有限的。如果a[i]的值域最大是maxVal那我完全可以统计在l到r这个区间里每一种数值出现了多少次然后对每个出现的数值val单独算val的k次方再乘上它出现的次数最后累加就行。这个做法的核心是“把同样的数合并计算”。比如区间里数字7出现了80次那我只需要计算一次7^k再乘80而不是傻傻地把7^k算80次。复杂度一下子从区间长度降低为值域大小。而“统计l到r区间里某个数出现多少次”这件事正好可以用前缀和来做——不是对原数组的值做前缀和而是对下标做前缀和维护一个二维数组cnt[val][i]表示前i个位置中数值val出现的次数。查询l到r时用cnt[val][r]减cnt[val][l-1]即可。这个二维数组的空间是maxVal乘以nmaxVal如果只有100或者1000那内存完全扛得住。到这一步整个方案的轮廓已经出来了预处理每种数值的出现次数前缀和查询时遍历值域内的所有数值对每个非零计数的数值做一次快速幂累加取模。2.4 为什么这题不能用线段树的底层逻辑很多人在牛客评论区里问“这题能不能用线段树”我想统一说说这个问题。线段树的核心优势是支持动态修改和区间查询它的本质是利用结合律把多个子区间的信息合并成父区间的信息。加法、取max、取min这些操作都能合并因为你可以通过子区间的结果直接推导区间结果。但“次方和”这个操作不具备这种可合并性。你已知左半部分每个数的平方和是A右半部分每个数的平方和是B但你完全不知道整个区间的三次方和是多少因为A和B里不包含每个数本身的信息。除非线段树每个节点把每个可能k下的次方和都存一份那又回到了空间爆炸的循环里。学术点说就是这类操作不具备“幂等合并”的数学性质数据结构上的通用武器反而使不上劲。3. 核心实现完整代码与关键细节讲解3.1 第一步先确认数据范围再决定方案写代码之前一定先读清楚数据范围这是老生常谈但真的致命。我在这题上就吃过亏一开始没注意a[i]的值域限制写了一个自以为很巧妙的方案结果发现值域根本不是我预想的那么小白写半天。正常流程是这样先看n和m的量级如果都是1e5那每个查询跑O(maxVal)是可以接受的再看a[i]的最大值maxA如果maxA在1000以内甚至更小直接用二维前缀和计数方案如果maxA很大比如1e5那你需要做离散化把出现过的数值压缩成连续的编号再走同一个方案。离散化就是给每个不同的值分配一个新编号处理起来也很快。这一步不是可选项是必选项先花30秒看范围能省后面两小时。3.2 费马小定理把超大指数安全地降下来这题还有一个隐藏很深的数学细节就是k本身可以非常大。计算val的k次方时如果k是1e9级别快速幂的log k大概30次运算其实也能接受。但如果k给出的是1e18甚至更夸张那就要考虑用费马小定理做指数降幂。因为模数是1e97它是一个质数。费马小定理说当mod是质数p且val不是p的倍数时val的(p-1)次方对p取模等于1。这意味着指数部分可以按p-1取余也就是把k替换成k%(p-1)幂运算的结果不变。但对val恰好是p倍数的情况要特判此时val^k对p取模等于0可以直接跳过。注意我这里的p就是1e97所以p-1等于1e96。这个降幂步骤看起来多此一举但它在k特别大的时候是救命稻草。而且它有一个额外的好处降幂之后指数最多不超过1e96快速幂的循环次数是固定的30多次时间复杂度完全可控不用在指数上再出幺蛾子。3.3 快速幂递归写法与迭代写法怎么选快速幂的原理一句话就能讲清楚把指数看成二进制每位上的1表示需要把当前底数的对应幂次乘进结果里。比如算3的13次方13的二进制是1101也就是841所以3^13 3^8乘3^4乘3^1三个数一乘就行。我习惯用迭代写法因为不用怕递归深度问题而且代码更紧凑。写的时候有两点血泪教训一是底数在乘法前要先取一次模防止底数本身已经巨大二是每一步乘法都要开long long否则两个1e9量级的数一乘直接溢出int变成负数结果全错。有些人在快速幂里写成int mid base * base % mod这行看着没毛病实际上乘完就炸了必须写成long long。快速幂还有个易错点是当指数为0时任何数的0次方等于1但底数如果是0的话0的0次方在数学上是未定义的编程题里一般不用纠结这个统一返回1就行。不过要是底数为0且指数大于0快速幂算出来也自然是0不用特殊处理。3.4 完整参考代码C实现直接看我当时写过的可运行版本代码结构分成预处理、查询、快速幂三块。各个部分之间的数据关系我尽量在注释里写清楚。#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 1000000007LL; ll n, m; vectorll a; vectorvectorint cnt; // cnt[val][i]: 数值val在前i个位置出现次数 int maxVal; // 快速幂计算 base^exp mod MOD ll fastPow(ll base, ll exp) { ll result 1; base % MOD; while (exp 0) { if (exp 1) result result * base % MOD; base base * base % MOD; exp 1; } return result; } // 用费马小定理降幂exp 对 MOD-1 取余 ll expMod(ll exp) { if (exp MOD - 1) { return exp % (MOD - 1); } return exp; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; a.resize(n 1); maxVal 0; for (int i 1; i n; i) { cin a[i]; if (a[i] maxVal) maxVal a[i]; } cnt.assign(maxVal 1, vectorint(n 1, 0)); for (int v 0; v maxVal; v) { for (int i 1; i n; i) { cnt[v][i] cnt[v][i - 1] (a[i] v ? 1 : 0); } } while (m--) { ll l, r, k; cin l r k; ll e expMod(k); ll ans 0; for (int v 0; v maxVal; v) { int times cnt[v][r] - cnt[v][l - 1]; if (times 0) continue; // 特判v 是 MOD 的倍数时v^k 为 0 if (v % MOD 0) continue; ll powVal fastPow(v, e); ans (ans powVal * times % MOD) % MOD; } cout ans \n; } return 0; }上面这段代码里有几个地方我想单独拎出来解释。cnt数组我用vector套vector来开因为值域maxVal在运行时才知道不能直接写静态二维数组。预处理cnt的时候复杂度是maxVal乘n如果maxVal是1000n是1e5那就是1e8次遍历有一点压力但能跑本地测试大概一秒多如果maxVal是100那非常轻松。查询部分的循环从0遍历到maxVal这是值域枚举遇到计数为0的数值直接跳过。为什么可以跳过因为区间里没出现过的数值谈不上贡献算了也是白算。这个剪枝极其重要没有它你的复杂度会凭空多出一大截。3.5 复杂度分析到底快在哪里暴力做法是O(m乘区间长度乘log k)区间长度平均可能是n/2总操作量爆炸。而优化后预处理阶段是O(maxVal乘n)每次查询是O(maxVal乘log k)。如果maxVal是100n和m都是1e5预处理1e7次操作每次查询100次快速幂也就是1e5乘100乘30等于3e8次运算这个量级在OJ上是可以过的稍微优化下常数就行。如果maxVal是1000那每次查询就是1000次快速幂1e5个查询就是1e8次快速幂每个快速幂30次循环总共3e9这就要卡时间了。所以这也是为什么我反复强调先看值域范围值域直接决定这个方案能不能用不是所有的题都能无脑套这个模板。4. 实战排坑这道题我真实踩过的那些坑4.1 减法取模的负数陷阱区间计数的时候cnt[v][r]减去cnt[v][l-1]是正常整数减法这个没问题。但最后累加答案时如果你在做减法形式的取模运算比如某个值模完是5另一个是8减出来是负3直接取模在C里会得到负数输出就会是错的。虽然这题最终的ans累加用的是加法取模但中间如果涉及减法一定要写成(ans - sub MOD) % MOD的形式。这个坑特别经典我在牛客评论区见过好几个人问为什么输出一堆负数十有八九就是忘了加MOD。你把这个习惯刻进DNA以后做任何取模题都能少踩一个坑。4.2 long long 溢出看似小事实则全盘皆输快速幂里base等于1e9左右乘起来直接超过2的31次方也就是int的上限。你用int存中间结果那一刻值就已经错了后面再怎么取模都救不回来。我当时排查这个问题花了快半小时因为单步调试看不出问题输出中间量才发现在乘法那里溢出成了负数。这类问题的排查思路很固定如果运算涉及两个可能接近1e9的数相乘中间量必须开long long如果涉及1e18量级的乘法long long也不够得用快速乘或者__int128。取模题目里这个规律放之四海而皆准记牢。4.3 0的次方与整除模数的特殊情况费马小定理降幂有个前提就是底数不能是模数的倍数。一旦v等于1e97或者它的倍数v^k对模数取模恒等于0如果你还按费马小定理去降幂底数取余后直接变成0算出来变成0的几次方结果倒也是0但逻辑上是有问题的。更麻烦的是v等于0本身0的0次方这种边界要提前想清楚。我最初写代码的时候没有特判v%MOD0这一行虽然测试数据没卡出来但这种隐患在正式笔试里很容易变成隐藏的扣分点。做题的时候别只看测试用例过没过把数学边界捋一遍再提交这个习惯很值钱。4.4 输入输出优化容易被忽略的隐形超时牛客的OJ对cin和cout的兼容性还算好但当你跑1e5级别的查询每次输出一行如果不关同步流cin和cout的开销能让你直接超时。我在代码开头写了ios::sync_with_stdio(false)和cin.tie(0)这两行几乎是我所有C刷题代码的标配。如果你的代码逻辑完全正确但超时第一个怀疑对象就是输入输出。有些同学喜欢用scanf和printf也行但混用cin和scanf会出问题别两边都用。我的习惯是统一用cin加关同步流代码写起来舒服性能也够。4.5 调试技巧构造对拍数据验证正解写这类数学性较强的题最怕的就是思路有问题但代码恰好过了样例。我的习惯是本地写一个暴力版本再用随机数据对拍两边结果一致才敢提交。对拍脚本用Python写很快生成随机n和m暴力算一次正解算一次跑几百组数据对比输出有差异就停下来看。这个方法看起来笨但它能帮你发现所有边界情况。尤其是计数前缀和这种逻辑下标差一还是差二l等于1还是等于r这些细枝末节用对拍一跑全都现原形比自己瞪着眼找快得多。5. 从区间次方和延伸出去一类题的通用解法思维5.1 区间查询题型的判断框架做完这道题我最大的收获不是背住了一个模板而是建立了一个判断框架。以后再遇到区间查询类的题目我第一反应是看操作性质这个查询结果能不能由子区间结果合并得到能合并考虑线段树或树状数组不能合并考虑每个元素在区间内怎么单独贡献然后想办法批量处理同类元素。次方和属于典型的“单点贡献型”区间问题因为每个数的贡献只取决于它自己是几和别人的关系不大。这种问题一旦值域受限统计出现次数加快速幂就是最标准的解法。换个角度说看到“区间内每个元素做某个运算再求和”这种描述值域允许的话优先想计数前缀和。5.2 同类题型的举一反三这个模板稍加变形能解很多题。比如区间内每个数乘自己的次数再求和就是先统计频率再用频率乘数值区间内不同数的个数直接用去重前缀和就能做区间内众数也可以用计数前缀和加遍历值域去做。它们的共同特征都是“值域可控加计数合并”。如果你做多了会发现这类题的根源其实是离散化思想把大量重复的运算结果缓存起来复用。它和动态规划有异曲同工的地方都是拿空间换时间但这里换得更巧妙不是存所有状态而是只存值得存的状态。5.3 刷题复盘的正确姿势代码只是结果思路链条才是资产我刷牛客刷到中期一个特别大的体会是题量堆到一定程度以后收获主要来自复盘而不是刷题本身。像区间次方和这道题真正值钱的不是那几十行代码而是从“线段树”到“计数前缀和”的思路转变过程。你如果只是对着别人的题解把代码抄一遍下次遇到换个马甲照样不会。我的复盘模板一般分三问第一问我最初的思路错在哪是什么条件让它失效第二问正解的核心洞察是什么它抓住了题目的哪个特殊性质第三问这个洞察还能用到哪些场景。把这三问答清楚这道题才算真正消化成你自己的。这份牛客刷题记录2里区间次方和是其中最典型的案例我把它放在第一篇来写。最后再分享一个我个人的实操习惯每次做完这种带数学细节的题我会把题目的特殊条件单独摘出来记在一个小本子里比如“值域小就用计数前缀和”“模质数考虑费马降幂”。这些条件就是题目的命门下次看到直接条件反射省去重新推导的时间。刷题并不是比谁做得快而是比谁见过的命门多见得多了自然出手就有把握。