这篇牛客刷题记录2记录的是我最近两周在牛客网上集中刷区间次方和的完整过程。本来只想随便找几道题保持手感结果这个看起来不起眼的考点把前缀和、快速幂、取模、数据结构更新全都串了起来。如果你也在牛客刷题或者正在准备校招笔试这篇文章里踩过的坑和整理过的模板应该能帮上忙。我所说的区间次方和指的是这样一类题给定一个数组多次询问某个区间内每个数的k次方之和结果对某个数取模。牛客上这类题出现频率不低但网上专门分析的不多很多人一上来就暴力求解然后被评测机无情打回。这篇记录就是围绕这类题展开的。文章适合三类人刚接触OJ想系统刷题的初学者、准备笔试想要快速抓重点的求职者以及像我一样喜欢记录复盘的老刷题人。内容会包含暴力解法的局限、前缀和优化、动态修改场景下的树状数组方案还有我在牛客OJ上翻过车的几个真实细节。我的记录风格向来是先讲为什么再讲怎么做所以你会看到不少思考过程和失败案例而不是干巴巴的代码。如果你只想要模板可以直接跳到第四节如果愿意跟着我的思路走那我们从选题原因聊起。1. 为什么挑了区间次方和这个专题来啃先说选题的由来。我刷题有个习惯每隔一段时间会去牛客的搜索框和讨论区看看大家在聊什么。那天搜“刷题”发现热词区间次方和排在前列点进去一看相关题目不少但题解区要么只说暴力要么上来就甩一个线段树模板中间的分析其实挺缺的。这反而激起了我的兴趣。刷题最怕的就是只会背模板不懂背后的演化过程而区间次方和恰恰是那种能逼你理解“为什么需要优化”的好题。更重要的是区间次方和是一个典型“可扩展”的考点。它表面上是一个数学题但实质是数据结构题。从静态数组的多次查询到允许单点修改的动态场景难度可以平滑过渡。刷这类题相当于用一种题型把好几个基础算法复习一遍性价比很高。而且它和传统的前缀和题不一样——多了个次方操作让初次接触的人容易踩坑但一旦搞明白自信心会大幅提升。我的选题标准有三个第一题目在笔试中出现频率够高第二解法有梯度能从暴力到前缀和再到树状数组第三边界条件足够多能练出调试手感。区间次方和全都满足。于是我把这个专题定为牛客刷题记录2的攻坚目标。具体节奏我这样安排一周半时间每天抽1到2小时最多做3道同类题。第一道无所谓先随便选从第二道开始按难度排序。每道题必须经历三个环节——先提交一个暴力版本保证理解题意再实现优化版本最后记录错误点。这个节奏比较适合上班族太密了容易疲劳太散又形不成记忆。1.1 从热搜词里发现的高频考点这里有个小方法论不要漫无目的地刷题而是从社区的热搜词反推题目类型。像牛客 区间次方和这个词被大量搜索说明很多人在这个考点上卡住了。通常被反复搜索的题目不是题目描述有歧义就是解法的某个细节容易出错。去刷这些题收益往往比随机刷十道水题高。我认识不少刷了上千题的人成绩却一般原因就是他们从不关注社区热词只顾闷头刷刷完就忘。所以我现在每开始一个新专题第一步不是打开题目列表而是看牛客讨论区的一周热词。哪些词上榜我就优先把跟这些词相关的题目拉出来做。这个方法听起来很功利但刷题本身就是功利的事——为了笔试面试为了更快的解题速度不走捷径反而不明智。1.2 区间次方和到底考什么这类题的核心句子通常是“给定长度为n的数组am次询问每次给定l、r、k求Σ从il到r的a[i]^k对P取模。”看第一眼会觉得是数学题但其实考的是查询效率。暴力思路很简单每次循环从l到r累加k次方。但n和m一旦都到10万O(nm)的复杂度必超时。优化方向通常是前缀和、树状数组或线段树而k值的大小又决定了预处理方式。这里有个关键点如果k固定比如始终是平方和那么只需要一个普通的前缀和数组如果k是每次查询时给出的并且k的范围较小比如1到5那么可以预处理多个前缀和数组每个k对应一个如果k的范围很大那就要考虑更复杂的数论或数据结构方案了。牛客上最常见的版本还是固定k或者k很小所以我先从简单版本剖析。1.3 我的选题标准与刷题节奏前面说了三个标准实际执行时还要注意不要贪多。我给自己定的目标是一周半刷完十道左右的同类型题而不是一天十道。因为刷题的本质是建立条件反射看到区间查询想到前缀和看到修改想到数据结构。这个反射需要时间固化一天刷十道只会让大脑过载第二天全忘。另外我建议每道题投入的时间上限是两小时。如果两小时还没思路就果断看题解然后把题解的思路自己重新推一遍。很多初学者有个误区觉得看题解是耻辱其实真正的高手都会看题解关键在于是不是真的看懂并且能复现。我刷这道区间次方和时第一道暴力第二道前缀和第三道一上来就卡住了最后看了题解才想到预处理多个k的prefix数组。正是那次看题解让我彻底理解了这类题共同的框架。2. 暴力解法跑通之后我开始琢磨前缀和2.1 先看题目长什么样我挑的是一道经典的静态区间次方和题抽象出来大概是这样给你一个长度为n的整数数组a然后有m次查询每次查询给出l、r让你输出a[l]^2 a[l1]^2 ... a[r]^2结果对1e97取模。n和m都最大10万a[i]最大10^9。题目本身不复杂但它默认你必须把复杂度压到O(nm)或O((nm)logn)级别否则就是超时。之所以拿平方举例是因为平方是次方里最容易书写理解的而且平方后的数据范围变化能讲清楚溢出问题。后面我会顺带说明k不为2的情况。2.2 暴力循环为什么过不了很多人拿到这题第一反应就是直接模拟我也是。每次查询从l到rfor循环累加代码十几行就能写完。比如用Python写MOD 10**9 7 n, m map(int, input().split()) a list(map(int, input().split())) for _ in range(m): l, r map(int, input().split()) ans 0 for i in range(l - 1, r): ans (ans a[i] * a[i]) % MOD print(ans)逻辑没问题但n和m都是10万时最坏情况下每次查询都要遍历整个数组总运算量是10万乘以10万等于1e10次。这个数量级在Python里完全跑不动即使C也要好几秒牛客的判题机大概率会给你一个TLE。暴力解法唯一的用处是当验证工具在写优化算法之前先跑一遍暴力确保自己理解题意正确。2.3 前缀和数组的构建与查询暴力慢在重复计算。如果每次都重新累加从左到右的平方和等于把之前算过的东西再算一遍。前缀和的核心思路就是“算一次用多次”:提前把从第一个元素到当前位置的累计平方和存起来查询时做一次减法就能拿到区间和。先构建pre数组pre[i]表示数组前i个元素的平方和1-based索引。代码如下MOD 10**9 7 n, m map(int, input().split()) a list(map(int, input().split())) pre [0] * (n 1) for i in range(1, n 1): pre[i] (pre[i - 1] a[i - 1] * a[i - 1]) % MOD for _ in range(m): l, r map(int, input().split()) ans (pre[r] - pre[l - 1]) % MOD print(ans)构建pre的复杂度是O(n)每个查询是O(1)整体O(nm)10万的数据量瞬间就能跑完。注意这里我用的是1-based的pre查询区间[l,r]对应pre[r]减去pre[l-1]。这个下标的边界处理是整个题目最容易出错的地方后面我会单独说。如果k不固定而是最多到K比如K5我们可以把二维前缀和数组提前建好K 5 pre [[0] * (n 1) for _ in range(K 1)] for k in range(1, K 1): for i in range(1, n 1): pre[k][i] (pre[k][i - 1] pow(a[i - 1], k, MOD)) % MOD # 查询 for _ in range(m): l, r, k map(int, input().split()) ans (pre[k][r] - pre[k][l - 1]) % MOD print(ans)预处理复杂度O(Kn)查询O(1)。如果K不大这是一个非常实用的模板。2.4 带取模的前缀和几个容易踩的坑第一个坑是取模负数。C里(pre[r] - pre[l-1]) % MOD可能得到负数因为减法之后的结果小于0。很多人会忘记先加上MOD再取模。Python的%运算天然保证非负所以写Python会很省心但如果面试要求写C必须写成(ans MOD) % MOD。第二个坑是数据溢出。a[i]本身可以到10^9平方后是10^18远超int的2.1亿上限。用C必须开long long用Python则不存在这个问题但如果你习惯用C刷题这个问题很致命。我身边就有同学在牛客上提交时因为int溢出WA了三次改成long long立刻AC。第三个坑是pre的初始化大小。pre长度应该是n1pre[0]0。如果你习惯0-based的数组想直接用pre[r]表示到r的累加和那查询区间[l,r]就是pre[r]-pre[l-1]注意r对应a[r-1]。我建议所有前缀和题统一用1-based因为这样下标语义最清晰避免混乱。3. 牛客OJ的评测陷阱不是思路对就能AC3.1 输入格式里藏着的坑牛客和力扣一个很大的区别在于牛客很多题目要求你自己处理全部输入没有提供封装好的方法接口。这意味着输入格式稍不留神就会读错。比如有的题目会写输入含多组数据每组数据第一行是n和m如果你只按单组数据读取提交后大概率WA。在Python里我习惯一次性把所有内容读进来然后按token切分而不是逐行input()这样可以避免空行和多余字符的干扰。代码是这样的import sys data list(map(int, sys.stdin.buffer.read().split()))然后按顺序从data里取出n、m和数组a。这种方法在数据量达到10万级别时比逐行input()快出好几个数量级。3.2 数据范围与int溢出前面说过平方和会爆int。但还有一个隐蔽的点a[i]^k当k3或更高时即使a[i]只有10^5立方也是10^15同样超int。因此只要涉及次方就默认开long long。在Python里则要注意pow(a, k, MOD)的用法直接用a**k再取模虽然也行但当k很大时中间结果的生成会消耗大量时间和内存。写Python优先用内置的pow(a, k, MOD)它内部用了快速幂取模效率高得多。3.3 多组测试用例的复位问题牛客的题经常是多组输入处理完后可能还有下一组。如果你把pre、bit这类全局数组定义在while循环外面下一组数据进来时没有重新初始化残留的上一次数据就会污染结果。我的解决办法是在每个测试用例的读取完成后立刻重新创建并填充pre或者把pre的赋值操作放进循环体内部。这一点结合系统测试用例特别容易漏——本地跑单组数据没问题一提交就WA而且报错信息也模糊只能靠反复读题判断。3.4 一次WA的完整排查过程我印象最深的一次WA是一道带多组输入的区间次方和题。本地随便测都正确一交上去就是WA。我先把代码改成sys.stdin.buffer.read()统一读入问题依旧。然后我怀疑是不是模数写错又确认了题目给的MOD是998244353而不是常用的1e97。我一直没发现真正问题后来把题目的样例完整复制下来逐字节比对才意识到样例第一行后面有一个空行而我用read().split()处理时空行被自动忽略了理论上不会出错。最终排查下来问题出在我没有在每组数据结束时把输出清空其实输出没问题。最后我重置了所有变量在每组数据的开头重新初始化pre提交后AC了。这个经历让我养成了一个习惯只要代码设计合理但仍然WA就优先检查“是否按照题目要求处理了多组输入”。牛客的出题风格和力扣很不一样它模仿的是真实笔试题环境喜欢用多组测试用例来增加干扰。你现在觉得烦等真正上笔试系统的时候反而会觉得熟悉。后来我又遇到过一个因为下标混乱导致的WA我把查询的l和r直接用在了0-based数组上但pre是1-based导致差一位。那次之后我给自己定了一条规则所有涉及区间查询的代码先画一个长度为5的数组手动模拟一次查询再动手写。凡是这样做了的题后面基本没在边界上错过。4. 当区间查询遇上动态修改前缀和就不够用了4.1 题目扩展单点修改区间查询静态数组的原题练完下一道升级题来了在区间次方和的基础上增加一种操作——修改a[pos] val之后继续查询区间次方和。如果还是用前缀和每次更新pos位置后需要重新计算从pos到n的所有pre值最坏O(n)。当更新次数也到10万时整体复杂度又是O(nm)级别相当于退化回了暴力。这时候就需要支持单点修改、区间查询的数据结构。最自然的选择是树状数组或线段树。这道题的场景是“单点改、区间查”树状数组完全够用而且代码量比线段树小很多。我选用树状数组作为重点讲解对象。4.2 树状数组的核心思想树状数组擅长维护前缀和它用lowbit把数组划分成不同长度的块。查询前缀和时每次“去掉最右边的1”把对应区间的和累加起来单点更新时每次“加上最右边的1”把所有覆盖该点的区间都更新一遍。两个操作都是O(logn)级别。对于区间次方和我们需要维护的不是a[i]本身而是a[i]^k。也就是说树状数组第i个位置存储的是当前a[i]的k次方。这样查询[l,r]就是前缀和函数求到r的累积值减去求到l-1的累积值修改a[pos]时先计算delta new_val^k - old_val^k然后在pos位置上增加delta。4.3 树状数组代码模板我用Python写了一个通用模板支持单点加和区间和查询并且处理了取模。MOD 10**9 7 class BIT: def __init__(self, n): self.n n self.tree [0] * (n 1) def add(self, idx, delta): while idx self.n: self.tree[idx] (self.tree[idx] delta) % MOD idx idx -idx def prefix_sum(self, idx): res 0 while idx 0: res (res self.tree[idx]) % MOD idx - idx -idx return res def range_sum(self, l, r): return (self.prefix_sum(r) - self.prefix_sum(l - 1)) % MOD # 初始化 bit BIT(n) for i in range(1, n 1): bit.add(i, pow(a[i - 1], k, MOD)) # 查询 print(bit.range_sum(l, r)) # 修改 a[pos] val (pos是1-based) delta (pow(val, k, MOD) - pow(a[pos - 1], k, MOD)) % MOD a[pos - 1] val bit.add(pos, delta)这里有个细节delta可能是负数我用% MOD把它变成正数后再加入树状数组。Python的%保证结果非负所以直接这样写没关系如果用C写成((new-old)%MODMOD)%MOD更安全。4.4 为什么这里不选线段树有朋友会问既然线段树也能做为什么选树状数组我的判断标准很简单如果只需要单点修改和区间查询树状数组的代码量不到线段树的一半常数也更小。线段树虽然更通用能处理区间修改、区间最大值最小值等复杂场景但在这道题里属于杀鸡用牛刀。数据结构的选型应该看需求复杂度而不是越高级越好。如果题目变成了“区间内所有元素统一加上一个值再查询区间次方和”那就是区间修改加区间查询这时树状数组得借助差分思路麻烦程度直线上升线段树才是更合理的选择。在牛客刷题时我会把这类选择标准写进笔记方便以后快速决策。5. 我的刷题笔记整理法与复盘机制5.1 笔记里记什么、不记什么很多人的刷题记录只是把代码贴到收藏夹里这没有意义。我的笔记是用一个Markdown文件维护的每道题固定四部分题目特征、核心考点、踩过的坑、可复用模板。题目描述和完整代码我通常不记因为牛客网站上有我只需要写一句链接。重点记录的是这道题“为什么让我卡住”以及“我应该用什么思路快速切入”。记录的时候我会刻意设定一个期限当天晚上整理笔记不拖到第二天否则当时的思考细节就丢了。比如区间次方和这组题我在“核心考点”写的是“前缀和预处理取模边界”在“踩过的坑”写的是“多组输入未重置pre、减法取模为负”模板则放了一份前缀和数组初始化和查询的通用代码。下次再遇到类似题我只需要扫一眼模板就能想起来省去重新推一遍的时间。5.2 错题复盘的具体流程我每周日晚上抽一小时做复盘只做这一周错掉的题不看题解凭记忆把正确答案写出来。如果还是写错就说明题目的解法没有真正内化我会单独打上“优先级高”标签放到下周的复习列表里。这个过程看起来很笨但非常有效。我刚刷区间次方和时第一次提交就碰到多组输入的坑当时只记录了一下“下次注意”。那周复盘时我又写了同类型题结果还是卡在输入读取上这才逼着我彻底改成read().split()风格的模板。从那以后我再也没有因为输入格式丢过分。复盘还有一个好处你能直观看到自己哪些错误是“重复犯”的。我统计过前两周的题错因中约一半都是边界下标和取模问题。这说明刷题时真正需要死磕的往往不是算法思路本身而是这些细节处理。把这些高频错误汇总成一个“个人防坑清单”比多看十篇题解都有用。5.3 把同类题归拢区间类问题的套路总结刷了十几道区间次方和之后我对区间类基础题做了一个小的整理给自己总结了一套优先级判断流程看到区间查询先看数组是否动态变化。如果静态优先前缀和/差分k固定就一个prek有多种且范围小就多个pre。如果单点修改、区间查询优先树状数组。如果区间修改、区间查询再考虑线段树或树状数组差分。任何加减取模操作统一用“(原式)%MOD”C中防止负数还要加MOD再模。这套流程参考了labuladong刷题笔记里的框架思路但基于牛客的实际题目做过微调。我觉得刷题笔记的最终价值就是形成这种属于你自己的“条件反射清单”而不是一堆不知道什么时候该用的模板。把同类题的共性抽出来才算是真正理解了这一类问题。6. 牛客、力扣、洛谷的刷题体验横向对比6.1 三者的题目风格差异这段时间在牛客刷题我也顺带比较了力扣和洛谷。牛客的题库和真实校招笔试题贴合度很高很多公司的招聘笔试直接使用牛客的系统所以题目风格偏向“实用”输入输出格式比较原始需要自己处理多组数据。力扣则更偏算法研究每道题给你一个现成函数接口核心考点集中在纯算法上对输入输出细节的考察较少。洛谷面向竞赛题目的思维难度梯度很大有很多能让人眼前一亮的偏题怪题。如果你是为了准备面试特别是国内大厂笔试牛客的优先级绝对应该提上来。因为面试和笔试环境里你面对的永远是ACM式输入输出而不是力扣那种优雅的函数签名。适应这种原始风格需要专门练。我在力扣上能轻松做出Hard第一次做牛客的中等题照样踩输入坑这就是环境差异。6.2 判题反馈与调试体验力扣的判题反馈相对友好出错了能直观看到输入输出和预期结果还有中文题解区。牛客的判题反馈比较死板只告诉你通过多少测试用例或者直接WA/TLE看不到具体用例。这意味着你必须自己构造边界数据。但反过来这种“黑盒”体验正好模拟了笔试现场锻炼你仔细读题和自测的能力。洛谷则介于两者之间很多题有spj或者提供部分数据提示题解也详细但整体更偏向竞赛查漏补缺。6.3 我的建议不同阶段怎么选平台我现在的习惯是日常专项训练用力扣因为它的题目分类和标签很完善适合按专题提升阶段性刷题和笔试冲刺用牛客因为能训练真实输入输出环境还可以直接刷公司真题额外拓展用洛谷找一些思维题来打破套路。这张表可以帮你快速定位自己应该选哪个平台维度牛客力扣洛谷主要场景校招笔试、公司真题算法专项、面试准备竞赛训练、思维拓展输入输出原始IO多组数据函数接口封装原始IO反馈体验黑盒判题看不到用例能看到错误用例部分题可看测试点题解风格偏实用节奏快分类细致讨论活跃由简到难覆盖面广适合人群求职者、应届生算法学习爱好者竞赛党、想硬核提升的人我的建议是不要只吊在一个平台上。牛客刷题记录系列我会一直写是因为它最能暴露笔试环境里那些“非算法”问题。这些问题在力扣里永远碰不到但恰恰是笔试拉开差距的地方。刷题不应只求AC数量像牛客这样能模拟真实环境的地方多刷才有价值。这篇记录写到这我最大的体会是区间次方和看起来只是一个考点但顺着它一路挖下去你会发现前缀和、快速幂、取模运算、树状数组、线段树选型全都被串起来了。刷题最开心的时刻不是看到Accepted而是某天看到一道新题你能一眼看出它该用什么数据结构并且连边界条件都心中有数。牛客的题库里还有大量类似的多层考点题下一篇我准备去啃二分答案到时候再回来接着记录。如果你最近也在刷这一块欢迎在评论区留一句你踩过的坑咱们互相补漏。
这篇牛客刷题记录2记录的是我最近两周在牛客网上集中刷区间次方和的完整过程。本来只想随便找几道题保持手感结果这个看起来不起眼的考点把前缀和、快速幂、取模、数据结构更新全都串了起来。如果你也在牛客刷题或者正在准备校招笔试这篇文章里踩过的坑和整理过的模板应该能帮上忙。我所说的区间次方和指的是这样一类题给定一个数组多次询问某个区间内每个数的k次方之和结果对某个数取模。牛客上这类题出现频率不低但网上专门分析的不多很多人一上来就暴力求解然后被评测机无情打回。这篇记录就是围绕这类题展开的。文章适合三类人刚接触OJ想系统刷题的初学者、准备笔试想要快速抓重点的求职者以及像我一样喜欢记录复盘的老刷题人。内容会包含暴力解法的局限、前缀和优化、动态修改场景下的树状数组方案还有我在牛客OJ上翻过车的几个真实细节。我的记录风格向来是先讲为什么再讲怎么做所以你会看到不少思考过程和失败案例而不是干巴巴的代码。如果你只想要模板可以直接跳到第四节如果愿意跟着我的思路走那我们从选题原因聊起。1. 为什么挑了区间次方和这个专题来啃先说选题的由来。我刷题有个习惯每隔一段时间会去牛客的搜索框和讨论区看看大家在聊什么。那天搜“刷题”发现热词区间次方和排在前列点进去一看相关题目不少但题解区要么只说暴力要么上来就甩一个线段树模板中间的分析其实挺缺的。这反而激起了我的兴趣。刷题最怕的就是只会背模板不懂背后的演化过程而区间次方和恰恰是那种能逼你理解“为什么需要优化”的好题。更重要的是区间次方和是一个典型“可扩展”的考点。它表面上是一个数学题但实质是数据结构题。从静态数组的多次查询到允许单点修改的动态场景难度可以平滑过渡。刷这类题相当于用一种题型把好几个基础算法复习一遍性价比很高。而且它和传统的前缀和题不一样——多了个次方操作让初次接触的人容易踩坑但一旦搞明白自信心会大幅提升。我的选题标准有三个第一题目在笔试中出现频率够高第二解法有梯度能从暴力到前缀和再到树状数组第三边界条件足够多能练出调试手感。区间次方和全都满足。于是我把这个专题定为牛客刷题记录2的攻坚目标。具体节奏我这样安排一周半时间每天抽1到2小时最多做3道同类题。第一道无所谓先随便选从第二道开始按难度排序。每道题必须经历三个环节——先提交一个暴力版本保证理解题意再实现优化版本最后记录错误点。这个节奏比较适合上班族太密了容易疲劳太散又形不成记忆。1.1 从热搜词里发现的高频考点这里有个小方法论不要漫无目的地刷题而是从社区的热搜词反推题目类型。像牛客 区间次方和这个词被大量搜索说明很多人在这个考点上卡住了。通常被反复搜索的题目不是题目描述有歧义就是解法的某个细节容易出错。去刷这些题收益往往比随机刷十道水题高。我认识不少刷了上千题的人成绩却一般原因就是他们从不关注社区热词只顾闷头刷刷完就忘。所以我现在每开始一个新专题第一步不是打开题目列表而是看牛客讨论区的一周热词。哪些词上榜我就优先把跟这些词相关的题目拉出来做。这个方法听起来很功利但刷题本身就是功利的事——为了笔试面试为了更快的解题速度不走捷径反而不明智。1.2 区间次方和到底考什么这类题的核心句子通常是“给定长度为n的数组am次询问每次给定l、r、k求Σ从il到r的a[i]^k对P取模。”看第一眼会觉得是数学题但其实考的是查询效率。暴力思路很简单每次循环从l到r累加k次方。但n和m一旦都到10万O(nm)的复杂度必超时。优化方向通常是前缀和、树状数组或线段树而k值的大小又决定了预处理方式。这里有个关键点如果k固定比如始终是平方和那么只需要一个普通的前缀和数组如果k是每次查询时给出的并且k的范围较小比如1到5那么可以预处理多个前缀和数组每个k对应一个如果k的范围很大那就要考虑更复杂的数论或数据结构方案了。牛客上最常见的版本还是固定k或者k很小所以我先从简单版本剖析。1.3 我的选题标准与刷题节奏前面说了三个标准实际执行时还要注意不要贪多。我给自己定的目标是一周半刷完十道左右的同类型题而不是一天十道。因为刷题的本质是建立条件反射看到区间查询想到前缀和看到修改想到数据结构。这个反射需要时间固化一天刷十道只会让大脑过载第二天全忘。另外我建议每道题投入的时间上限是两小时。如果两小时还没思路就果断看题解然后把题解的思路自己重新推一遍。很多初学者有个误区觉得看题解是耻辱其实真正的高手都会看题解关键在于是不是真的看懂并且能复现。我刷这道区间次方和时第一道暴力第二道前缀和第三道一上来就卡住了最后看了题解才想到预处理多个k的prefix数组。正是那次看题解让我彻底理解了这类题共同的框架。2. 暴力解法跑通之后我开始琢磨前缀和2.1 先看题目长什么样我挑的是一道经典的静态区间次方和题抽象出来大概是这样给你一个长度为n的整数数组a然后有m次查询每次查询给出l、r让你输出a[l]^2 a[l1]^2 ... a[r]^2结果对1e97取模。n和m都最大10万a[i]最大10^9。题目本身不复杂但它默认你必须把复杂度压到O(nm)或O((nm)logn)级别否则就是超时。之所以拿平方举例是因为平方是次方里最容易书写理解的而且平方后的数据范围变化能讲清楚溢出问题。后面我会顺带说明k不为2的情况。2.2 暴力循环为什么过不了很多人拿到这题第一反应就是直接模拟我也是。每次查询从l到rfor循环累加代码十几行就能写完。比如用Python写MOD 10**9 7 n, m map(int, input().split()) a list(map(int, input().split())) for _ in range(m): l, r map(int, input().split()) ans 0 for i in range(l - 1, r): ans (ans a[i] * a[i]) % MOD print(ans)逻辑没问题但n和m都是10万时最坏情况下每次查询都要遍历整个数组总运算量是10万乘以10万等于1e10次。这个数量级在Python里完全跑不动即使C也要好几秒牛客的判题机大概率会给你一个TLE。暴力解法唯一的用处是当验证工具在写优化算法之前先跑一遍暴力确保自己理解题意正确。2.3 前缀和数组的构建与查询暴力慢在重复计算。如果每次都重新累加从左到右的平方和等于把之前算过的东西再算一遍。前缀和的核心思路就是“算一次用多次”:提前把从第一个元素到当前位置的累计平方和存起来查询时做一次减法就能拿到区间和。先构建pre数组pre[i]表示数组前i个元素的平方和1-based索引。代码如下MOD 10**9 7 n, m map(int, input().split()) a list(map(int, input().split())) pre [0] * (n 1) for i in range(1, n 1): pre[i] (pre[i - 1] a[i - 1] * a[i - 1]) % MOD for _ in range(m): l, r map(int, input().split()) ans (pre[r] - pre[l - 1]) % MOD print(ans)构建pre的复杂度是O(n)每个查询是O(1)整体O(nm)10万的数据量瞬间就能跑完。注意这里我用的是1-based的pre查询区间[l,r]对应pre[r]减去pre[l-1]。这个下标的边界处理是整个题目最容易出错的地方后面我会单独说。如果k不固定而是最多到K比如K5我们可以把二维前缀和数组提前建好K 5 pre [[0] * (n 1) for _ in range(K 1)] for k in range(1, K 1): for i in range(1, n 1): pre[k][i] (pre[k][i - 1] pow(a[i - 1], k, MOD)) % MOD # 查询 for _ in range(m): l, r, k map(int, input().split()) ans (pre[k][r] - pre[k][l - 1]) % MOD print(ans)预处理复杂度O(Kn)查询O(1)。如果K不大这是一个非常实用的模板。2.4 带取模的前缀和几个容易踩的坑第一个坑是取模负数。C里(pre[r] - pre[l-1]) % MOD可能得到负数因为减法之后的结果小于0。很多人会忘记先加上MOD再取模。Python的%运算天然保证非负所以写Python会很省心但如果面试要求写C必须写成(ans MOD) % MOD。第二个坑是数据溢出。a[i]本身可以到10^9平方后是10^18远超int的2.1亿上限。用C必须开long long用Python则不存在这个问题但如果你习惯用C刷题这个问题很致命。我身边就有同学在牛客上提交时因为int溢出WA了三次改成long long立刻AC。第三个坑是pre的初始化大小。pre长度应该是n1pre[0]0。如果你习惯0-based的数组想直接用pre[r]表示到r的累加和那查询区间[l,r]就是pre[r]-pre[l-1]注意r对应a[r-1]。我建议所有前缀和题统一用1-based因为这样下标语义最清晰避免混乱。3. 牛客OJ的评测陷阱不是思路对就能AC3.1 输入格式里藏着的坑牛客和力扣一个很大的区别在于牛客很多题目要求你自己处理全部输入没有提供封装好的方法接口。这意味着输入格式稍不留神就会读错。比如有的题目会写输入含多组数据每组数据第一行是n和m如果你只按单组数据读取提交后大概率WA。在Python里我习惯一次性把所有内容读进来然后按token切分而不是逐行input()这样可以避免空行和多余字符的干扰。代码是这样的import sys data list(map(int, sys.stdin.buffer.read().split()))然后按顺序从data里取出n、m和数组a。这种方法在数据量达到10万级别时比逐行input()快出好几个数量级。3.2 数据范围与int溢出前面说过平方和会爆int。但还有一个隐蔽的点a[i]^k当k3或更高时即使a[i]只有10^5立方也是10^15同样超int。因此只要涉及次方就默认开long long。在Python里则要注意pow(a, k, MOD)的用法直接用a**k再取模虽然也行但当k很大时中间结果的生成会消耗大量时间和内存。写Python优先用内置的pow(a, k, MOD)它内部用了快速幂取模效率高得多。3.3 多组测试用例的复位问题牛客的题经常是多组输入处理完后可能还有下一组。如果你把pre、bit这类全局数组定义在while循环外面下一组数据进来时没有重新初始化残留的上一次数据就会污染结果。我的解决办法是在每个测试用例的读取完成后立刻重新创建并填充pre或者把pre的赋值操作放进循环体内部。这一点结合系统测试用例特别容易漏——本地跑单组数据没问题一提交就WA而且报错信息也模糊只能靠反复读题判断。3.4 一次WA的完整排查过程我印象最深的一次WA是一道带多组输入的区间次方和题。本地随便测都正确一交上去就是WA。我先把代码改成sys.stdin.buffer.read()统一读入问题依旧。然后我怀疑是不是模数写错又确认了题目给的MOD是998244353而不是常用的1e97。我一直没发现真正问题后来把题目的样例完整复制下来逐字节比对才意识到样例第一行后面有一个空行而我用read().split()处理时空行被自动忽略了理论上不会出错。最终排查下来问题出在我没有在每组数据结束时把输出清空其实输出没问题。最后我重置了所有变量在每组数据的开头重新初始化pre提交后AC了。这个经历让我养成了一个习惯只要代码设计合理但仍然WA就优先检查“是否按照题目要求处理了多组输入”。牛客的出题风格和力扣很不一样它模仿的是真实笔试题环境喜欢用多组测试用例来增加干扰。你现在觉得烦等真正上笔试系统的时候反而会觉得熟悉。后来我又遇到过一个因为下标混乱导致的WA我把查询的l和r直接用在了0-based数组上但pre是1-based导致差一位。那次之后我给自己定了一条规则所有涉及区间查询的代码先画一个长度为5的数组手动模拟一次查询再动手写。凡是这样做了的题后面基本没在边界上错过。4. 当区间查询遇上动态修改前缀和就不够用了4.1 题目扩展单点修改区间查询静态数组的原题练完下一道升级题来了在区间次方和的基础上增加一种操作——修改a[pos] val之后继续查询区间次方和。如果还是用前缀和每次更新pos位置后需要重新计算从pos到n的所有pre值最坏O(n)。当更新次数也到10万时整体复杂度又是O(nm)级别相当于退化回了暴力。这时候就需要支持单点修改、区间查询的数据结构。最自然的选择是树状数组或线段树。这道题的场景是“单点改、区间查”树状数组完全够用而且代码量比线段树小很多。我选用树状数组作为重点讲解对象。4.2 树状数组的核心思想树状数组擅长维护前缀和它用lowbit把数组划分成不同长度的块。查询前缀和时每次“去掉最右边的1”把对应区间的和累加起来单点更新时每次“加上最右边的1”把所有覆盖该点的区间都更新一遍。两个操作都是O(logn)级别。对于区间次方和我们需要维护的不是a[i]本身而是a[i]^k。也就是说树状数组第i个位置存储的是当前a[i]的k次方。这样查询[l,r]就是前缀和函数求到r的累积值减去求到l-1的累积值修改a[pos]时先计算delta new_val^k - old_val^k然后在pos位置上增加delta。4.3 树状数组代码模板我用Python写了一个通用模板支持单点加和区间和查询并且处理了取模。MOD 10**9 7 class BIT: def __init__(self, n): self.n n self.tree [0] * (n 1) def add(self, idx, delta): while idx self.n: self.tree[idx] (self.tree[idx] delta) % MOD idx idx -idx def prefix_sum(self, idx): res 0 while idx 0: res (res self.tree[idx]) % MOD idx - idx -idx return res def range_sum(self, l, r): return (self.prefix_sum(r) - self.prefix_sum(l - 1)) % MOD # 初始化 bit BIT(n) for i in range(1, n 1): bit.add(i, pow(a[i - 1], k, MOD)) # 查询 print(bit.range_sum(l, r)) # 修改 a[pos] val (pos是1-based) delta (pow(val, k, MOD) - pow(a[pos - 1], k, MOD)) % MOD a[pos - 1] val bit.add(pos, delta)这里有个细节delta可能是负数我用% MOD把它变成正数后再加入树状数组。Python的%保证结果非负所以直接这样写没关系如果用C写成((new-old)%MODMOD)%MOD更安全。4.4 为什么这里不选线段树有朋友会问既然线段树也能做为什么选树状数组我的判断标准很简单如果只需要单点修改和区间查询树状数组的代码量不到线段树的一半常数也更小。线段树虽然更通用能处理区间修改、区间最大值最小值等复杂场景但在这道题里属于杀鸡用牛刀。数据结构的选型应该看需求复杂度而不是越高级越好。如果题目变成了“区间内所有元素统一加上一个值再查询区间次方和”那就是区间修改加区间查询这时树状数组得借助差分思路麻烦程度直线上升线段树才是更合理的选择。在牛客刷题时我会把这类选择标准写进笔记方便以后快速决策。5. 我的刷题笔记整理法与复盘机制5.1 笔记里记什么、不记什么很多人的刷题记录只是把代码贴到收藏夹里这没有意义。我的笔记是用一个Markdown文件维护的每道题固定四部分题目特征、核心考点、踩过的坑、可复用模板。题目描述和完整代码我通常不记因为牛客网站上有我只需要写一句链接。重点记录的是这道题“为什么让我卡住”以及“我应该用什么思路快速切入”。记录的时候我会刻意设定一个期限当天晚上整理笔记不拖到第二天否则当时的思考细节就丢了。比如区间次方和这组题我在“核心考点”写的是“前缀和预处理取模边界”在“踩过的坑”写的是“多组输入未重置pre、减法取模为负”模板则放了一份前缀和数组初始化和查询的通用代码。下次再遇到类似题我只需要扫一眼模板就能想起来省去重新推一遍的时间。5.2 错题复盘的具体流程我每周日晚上抽一小时做复盘只做这一周错掉的题不看题解凭记忆把正确答案写出来。如果还是写错就说明题目的解法没有真正内化我会单独打上“优先级高”标签放到下周的复习列表里。这个过程看起来很笨但非常有效。我刚刷区间次方和时第一次提交就碰到多组输入的坑当时只记录了一下“下次注意”。那周复盘时我又写了同类型题结果还是卡在输入读取上这才逼着我彻底改成read().split()风格的模板。从那以后我再也没有因为输入格式丢过分。复盘还有一个好处你能直观看到自己哪些错误是“重复犯”的。我统计过前两周的题错因中约一半都是边界下标和取模问题。这说明刷题时真正需要死磕的往往不是算法思路本身而是这些细节处理。把这些高频错误汇总成一个“个人防坑清单”比多看十篇题解都有用。5.3 把同类题归拢区间类问题的套路总结刷了十几道区间次方和之后我对区间类基础题做了一个小的整理给自己总结了一套优先级判断流程看到区间查询先看数组是否动态变化。如果静态优先前缀和/差分k固定就一个prek有多种且范围小就多个pre。如果单点修改、区间查询优先树状数组。如果区间修改、区间查询再考虑线段树或树状数组差分。任何加减取模操作统一用“(原式)%MOD”C中防止负数还要加MOD再模。这套流程参考了labuladong刷题笔记里的框架思路但基于牛客的实际题目做过微调。我觉得刷题笔记的最终价值就是形成这种属于你自己的“条件反射清单”而不是一堆不知道什么时候该用的模板。把同类题的共性抽出来才算是真正理解了这一类问题。6. 牛客、力扣、洛谷的刷题体验横向对比6.1 三者的题目风格差异这段时间在牛客刷题我也顺带比较了力扣和洛谷。牛客的题库和真实校招笔试题贴合度很高很多公司的招聘笔试直接使用牛客的系统所以题目风格偏向“实用”输入输出格式比较原始需要自己处理多组数据。力扣则更偏算法研究每道题给你一个现成函数接口核心考点集中在纯算法上对输入输出细节的考察较少。洛谷面向竞赛题目的思维难度梯度很大有很多能让人眼前一亮的偏题怪题。如果你是为了准备面试特别是国内大厂笔试牛客的优先级绝对应该提上来。因为面试和笔试环境里你面对的永远是ACM式输入输出而不是力扣那种优雅的函数签名。适应这种原始风格需要专门练。我在力扣上能轻松做出Hard第一次做牛客的中等题照样踩输入坑这就是环境差异。6.2 判题反馈与调试体验力扣的判题反馈相对友好出错了能直观看到输入输出和预期结果还有中文题解区。牛客的判题反馈比较死板只告诉你通过多少测试用例或者直接WA/TLE看不到具体用例。这意味着你必须自己构造边界数据。但反过来这种“黑盒”体验正好模拟了笔试现场锻炼你仔细读题和自测的能力。洛谷则介于两者之间很多题有spj或者提供部分数据提示题解也详细但整体更偏向竞赛查漏补缺。6.3 我的建议不同阶段怎么选平台我现在的习惯是日常专项训练用力扣因为它的题目分类和标签很完善适合按专题提升阶段性刷题和笔试冲刺用牛客因为能训练真实输入输出环境还可以直接刷公司真题额外拓展用洛谷找一些思维题来打破套路。这张表可以帮你快速定位自己应该选哪个平台维度牛客力扣洛谷主要场景校招笔试、公司真题算法专项、面试准备竞赛训练、思维拓展输入输出原始IO多组数据函数接口封装原始IO反馈体验黑盒判题看不到用例能看到错误用例部分题可看测试点题解风格偏实用节奏快分类细致讨论活跃由简到难覆盖面广适合人群求职者、应届生算法学习爱好者竞赛党、想硬核提升的人我的建议是不要只吊在一个平台上。牛客刷题记录系列我会一直写是因为它最能暴露笔试环境里那些“非算法”问题。这些问题在力扣里永远碰不到但恰恰是笔试拉开差距的地方。刷题不应只求AC数量像牛客这样能模拟真实环境的地方多刷才有价值。这篇记录写到这我最大的体会是区间次方和看起来只是一个考点但顺着它一路挖下去你会发现前缀和、快速幂、取模运算、树状数组、线段树选型全都被串起来了。刷题最开心的时刻不是看到Accepted而是某天看到一道新题你能一眼看出它该用什么数据结构并且连边界条件都心中有数。牛客的题库里还有大量类似的多层考点题下一篇我准备去啃二分答案到时候再回来接着记录。如果你最近也在刷这一块欢迎在评论区留一句你踩过的坑咱们互相补漏。
分析法实现IF-ELSE翻译程序：四元式与真假链回填)
