企业官网建设流程全解析

这周的牛客周赛 Round 135 打下来，最让我有记录欲望的，不是榜一大哥那几道压轴题，而是全场通过率最高的那道“区间次方和”。它看起来平平无奇，连搜索热词里都单独挂上了“区间次方和”这个名头，说明不少人在赛后被这道题卡过思路——或者说，卡在了“为什么我写的线段树TLE了”这个灵魂拷问上。我早年打周赛也是这个毛病：看到区间查询就条件反射上线段树，结果数据一大就吃瘪。

这篇文章就把 Round 135 里这道区间次方和题目从头到尾拆一遍：题意怎么还原、暴力错在哪、二维前缀表是怎么一步步推出来的、代码里有哪些容易被评测机判罚的细节，最后再聊聊这道题往深了能延伸出哪些变体。无论你是刚开始打周赛的新人，还是想找思路兜底的老人，这轮复盘应该都能给你一点东西。

1. 赛前摸底：Round 135 的题量、节奏和这题的定位

1.1 牛客周赛的常规节奏

牛客周赛这几年我基本没断过，赛制也摸得很清了。一般就是一次周赛五道题左右，比赛窗口两个小时，题目难度呈阶梯状往上铺：前面一两道是签到题，看懂了就能写；中间一两道需要一点思路转换；最后压轴的基本是那种“想通了一百行搞定、想不通一个半小时白给”的题。

Round 135 的整场节奏也大体如此，但这次有个很有意思的现象：往后压轴的题卡住了不少人，反而是中间这道“区间次方和”成了全场热度最高的讨论点。原因倒不是它多难，而是它的解法一旦选错，代码写起来会很顺手，但运行起来就非常难受——这种“看起来像套模板、实际上需要换个思路”的题，恰恰是周赛里最容易拉开差距的地方。

1.2 五道题的难度分布与策略取舍

我打周赛的固定策略是先花五分钟把五道题全部扫一遍，根据题型和通过人数预判难度，然后再决定动手顺序。Round 135 这次的整体分布大概是这样的：

• 第一题：模拟题，注意边界条件就能过，属于热身题。
• 第二题：稍微带点贪心或者双指针，难度不大。
• 第三题：区间次方和，看着很“数据结构”，实际是个前缀和的套路题，也是这次文章的主角。
• 第四题：需要一点数论或组合数学的底子，开始有人掉队。
• 第五题：压轴题，涉及比较复杂的维护逻辑，大部分人的时间都耗在这。

如果你一上来就扎进最后一题，很可能前三题都没时间好好拿分。我的建议是：先保证前四题稳定拿分，最后一题有多余时间再攻。区间次方和这道题因为处在第三题的位置，难度决定了它必然有一套“短平快”的正解，如果你在这里写出了一个又长又慢的线段树，那就已经走偏了。

1.3 为什么“区间次方和”这个热词能挂上榜单

赛后逛了一圈讨论区，发现“区间次方和”被反复提起，不是因为这题解法高深，而是它勾出了两类典型错误：一类是没看数据范围，直接对每个查询暴力遍历区间；另一类是看到“区间”就写线段树，结果更新和查询都有问题。这两类人在赛后的共同感受都是——我怎么就没想到前缀和。

说到底，区间查询类问题里，“前缀和”和“线段树”是一对需要分清的选项：前者处理的是静态数组的某种可减可加的区间聚合，后者处理的是动态更新和复杂聚合。Round 135 这题的数据是静态的、查询也不带修改，所以前缀和才是那套最匹配的方案，线段树属于杀鸡用了牛刀。

2. 区间次方和：题意还原与暴力解法的天花板

2.1 完整题目描述还原

先说清楚这题到底在问什么。基于 Round 135 的赛题内容和赛后讨论，我把它完整还原成下面这个形式，如果你手头正好有原题，可以对照着看：

给定一个长度为 n 的数组 a，下标从 1 开始。有 q 次查询，每次查询给出三个参数 l, r, p，你需要输出这个区间内所有元素的 p 次方之和：

sum_{i=l}^r a[i]^p

所有结果要对 1e9+7 取模。数据范围大概是 n、q 都在 10^5 这个量级，数组元素 a[i] 最大可以到 1e9，而 p 的取值范围是关键——它在 1 到 5 之间，非常小。

这个“p 在 1 到 5 之间”可不是乱写的，它就是整个题目的命门。很多人在赛桌上没注意到 p 的范围，或者注意到了但没往心里去。这里我提前划个重点：当你看到一个区间查询题目的某个参数范围特别小，比如 p 只有 1 到 5，那就意味着我们可以对每个可能的 p 分别维护一份前缀信息。数据结构题里的“小范围参数”，往往就是出题人留给你的钥匙。

2.2 直接模拟的复杂度估算

拿到题的一瞬间，最自然的写法就是：每次查询遍历一遍区间，对每个元素做快速幂，累加取模。伪代码大概长这样：

for (int i = l; i <= r; i++) { ans = (ans + fast_pow(a[i], p, MOD)) % MOD; }

看着没毛病，但你得算一笔账。单次查询的复杂度是区间长度乘以快速幂的 O(log p)。q 次查询在最坏情况下，可能每次都要查接近整个数组，也就是每次查询遍历接近 n 个数。那么总复杂度大约是：

O(q * n * log p)

把 n = 10^5、q = 10^5、log p 当作常数来算，这是 10^10 量级的运算。评测机每秒大概能跑 10^7 到 10^8 次简单操作，也就是说，理论上要跑到 100 秒以上，TLE 是板上钉钉的。

如果你用了时间复杂度更高的实现，比如每次查询里再嵌套一个复杂度更高的运算，那只会死得更快。所以第一步结论很明确：任何“每次查询都单独算一遍区间内的元素”的思路，都不可能在 10^5 的数据范围下过关。

2.3 为什么线段树在这题里不是最优解

接下来就得说说不少人的第二反应——线段树。这个反应太正常了，因为整个算法学习体系里，“区间查询”这个词几乎就是和线段树绑定的。但大家要记住一个前提：线段树的强项是支持“动态修改 + 区间查询”，而它的代价是每次操作都要 O(log n) 向下递归，常数还不小。也就是说，单次查询 O(log n) 的复杂度，在 q = 10^5 的情况下其实是能过的，问题不在这里。

真正的问题出在“次方和”这个聚合方式上。线段树合并子区间的信息，依赖的是一个可以快速合并的“结合律”。对于普通的区间和，两个子区间的和相加就是父亲的和，没问题。但对于区间次方和，如果题目要求你支持修改某个区间的值，比如把区间内所有元素统一加上一个偏移量 c，那么你要面对的就是 (x + c)^p 的展开，其中牵扯到二项式展开，旧的 p 次方和不能直接推导出新的 p 次方值。除非你同时维护 0 次方、1 次方、2 次方……一直到 p 次方的高阶矩，才能实现 O(p^2) 的合并，复杂度会随 p 上升得很厉害，而且写起来极易出错。

再说 Round 135 这题根本没有修改操作，数组是静态的，查询是纯读操作。对纯静态的区间查询，线段树能做的，前缀和往往能做得更好。那为什么很多人还是一眼写线段树？惯性思维。做题最怕的不是不会，而是会用一套“万金油”招数去套所有题，结果在简单题上反而花掉了大量时间。

3. 正解推导：从“次方很小”这个约束走到二维前缀表

3.1 核心观察：p 的取值范围是突破口

来把正解从头推一遍。这题最关键的一句话我已经反复强调了：p 只有 1 到 5。这意味着，查询虽然叫“区间次方和”，但事实上任意一次查询的次方参数只会落进 5 个可能值里。既然这样，我们就可以把一个大问题拆成 5 个子问题：

• 区间内所有元素的 1 次方和（也就是普通的区间和）
• 区间内所有元素的 2 次方和
• 区间内所有元素的 3 次方和
• 区间内所有元素的 4 次方和
• 区间内所有元素的 5 次方和

每一个子问题单独看，都是一个标准的“静态数组区间求和”问题，而静态数组区间求和的标准解法，就是前缀和。如果有 5 个子问题，那我们就准备 5 张前缀和表，查询的时候根据 p 的值选对应那张表，然后用前缀和的经典减法公式 O(1) 出答案。

这个思路的本质上是一种维度拆解：把“次方参数 p”这个维度从查询里提出来，做成索引维度。很多区间题看起来复杂，其实就是因为多个维度纠缠在一起。你只要找出一个取值范围极小、可枚举的维度，把它拆出来作为一部分预处理空间，剩下的部分往往就变得平平无奇了。这类思想在算法题里非常常见，二维前缀、三维前缀也是同源的思路。

3.2 预处理表的构造细节

具体到实现，我们需要一张二维表，行对应次方数 p（0 到 5，共 6 行），列对应数组位置 i（1 到 n）。表中每个格子 pre[p][i] 的含义是：

从数组第 1 个元素到第 i 个元素的 p 次方之和，且对 MOD 取模。

换句话说：

pre[p][i] = (pre[p][i-1] + a[i]^p) % MOD

构造过程是两重循环，外层遍历 p，内层遍历数组下标 i，每次只需要做一次快速幂、一次加法和一次取模，总复杂度 O(P * n * log p)，其中 P 是 5。算一下数：5 * 10^5 * 3，也就是大约 150 万次运算，对评测机来说就是一眨眼的事。

写代码的时候要注意一个习惯问题：数组下标尽量从 1 开始，让 pre[p][0] = 0 作为天然边界。这样在查询时用减法公式不会出现“下标为负”的情况，逻辑上更顺。很多人习惯从 0 开始遍历数组，结果写查询的时候就得各种凑下标，不但容易写错，调试也麻烦。

3.3 查询公式与正确性证明

有了 pre 表，查询就非常干净了。对于一次查询 (l, r, p)，答案直接用这一行两个位置的前缀和相减：

ans = (pre[p][r] - pre[p][l-1]) % MOD

之所以敢这么做，是因为我们维护的“次方和”满足减法性质——前缀和的本质是累积，而累积可以“撤销”。我从 l 到 r 的和，等于前 r 项的和减去前 l-1 项的和，剩下的就是第 l 项到第 r 项的部分。这在数学上等价于“把区间外的那部分贡献扣掉”，非常直接。

但这里有个所有新手都会踩的坑：取模减法在 C++ 里可能得到负数。因为 pre 里存的是模意义下的值，如果 pre[p][l-1] 大于 pre[p][r]，相减得到的 ans 就是负的，直接输出就 WA 了。所以每次减法之后必须做一次修正：

ans = (pre[p][r] - pre[p][l-1] + MOD) % MOD;

先加上一个 MOD 再取模，就可以保证结果归到 [0, MOD) 区间内。这不仅仅是为了这题的通过，所有“前缀和减法取模”的问题都必须养成这个习惯。你可以在草稿纸上自己推理一下：pre[p][r] 和 pre[p][l-1] 都在 [0, MOD) 内，两者相减的取值在 (-MOD, MOD) 之间，加一个 MOD 之后就落在 (0, 2*MOD) 内，再取模就是正确结果。

4. 完整代码与取模、卡常这些容易翻车的细节

4.1 可直接提交的 C++ 代码

下面是我赛后整理出来的一版完整可提交的 C++ 实现。注释写得比较细，主要目的是让你看清每一步在干什么：

#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1e9 + 7; const int MAXP = 5; ll fast_pow(ll base, ll exp, ll mod) { base %= mod; ll res = 1; while (exp > 0) { if (exp & 1) res = res * base % mod; base = base * base % mod; exp >>= 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<ll> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } // pre[p][i] 表示前 i 个元素的 p 次方和，p 从 1 到 5 vector<vector<ll>> pre(MAXP + 1, vector<ll>(n + 1, 0)); for (int p = 1; p <= MAXP; p++) { for (int i = 1; i <= n; i++) { ll val = fast_pow(a[i], p, MOD); pre[p][i] = (pre[p][i-1] + val) % MOD; } } while (q--) { int l, r, p; cin >> l >> r >> p; // 如果 p 超出 1~5 的范围，说明题目数据不止一种情况，需要额外处理 if (p < 1 || p > MAXP) { // 这里通常是预留扩展，Round 135 中 p 始终在 1~5 内 } ll ans = (pre[p][r] - pre[p][l-1] + MOD) % MOD; cout << ans << '\n'; } return 0; }

核心不到 40 行，去掉输入输出就更短了。这就是“短平快”的典型代表，也是评测机上最稳定的写法。如果你在赛场上写出了比这个复杂得多的结构，请停下来想一想——是不是哪一步思路跑偏了。

4.2 快速幂里的溢出陷阱

可能有人会说，p 最大只有 5，为什么要写快速幂？直接用一个 for 循环乘 5 次不就行了。确实可以，而且更快。但我写 fast_pow 有一个原因：它天然处理了中途乘法溢出的问题。

关键在 a[i] 的最大值可以达到 1e9。你算 a[i]^5 的时候，如果直接用朴素乘法算完再取模，中间结果是 1e9 的 5 次方，也就是 1e45 级别，早就超出了 long long 的表示范围，会发生溢出，结果完全乱掉。所以每做一次乘法，都必须立刻对 MOD 取模，快速幂的内部本身就是每一步 mod 的，能保证中途数字始终在 long long 范围内。

当然，因为 p 很小，你也可以不写快速幂而直接用循环累乘，效果一样，代码可能更容易被新手看懂：

ll val = 1; for (int k = 0; k < p; k++) { val = val * a[i] % MOD; }

这个写法在 p 只有 1 到 5 时完全OK，且不引入任何额外的复杂度。实战里怎么顺手怎么来，关键是“每步取模”这个纪律要守住。

4.3 读入优化与内存布局

这题读入量是 n + 3q，n 和 q 都在 1e5 量级，总共不到 40 万次整数读入，用 cin 加加速配置是完全可以过的。我上面代码里已经写了：

ios::sync_with_stdio(false); cin.tie(nullptr);

这两行是 C++ 选手的肌肉记忆。不写的话，cin 每次读入都要和 C 标准输入输出同步，会慢上一个量级。每次周赛我都看到有人因为忘写这两行被卡掉不少分，真的是最冤的丢分方式。

内存方面，pre 表是 (5+1) * (n+1) 个 long long，大约是 6 * 1e5 * 8 字节 = 4.8 MB，完全没有压力。如果你用 int 存，可能会有溢出风险，建议直接开 long long，省心。

4.4 一个容易被忽略的边界：p=0 的情况

虽然 Round 135 这题我看到的版本 p 是从 1 到 5，但很多类似题会在某个测试点偷偷放 p=0。按数学约定，任何数的 0 次方都等于 1，包括 0 的 0 次方在某些编程语言里也返回 1。也就是说，如果查询参数 p 等于 0，答案就是区间长度 r - l + 1，连数组里的数长什么样都不需要管。

如果你在赛场上遇到 p=0 的情况，最稳的处理是把它单独判掉：

if (p == 0) { cout << (r - l + 1) % MOD << '\n'; continue; }

如果你不加这个判断，直接用快速幂去算 a[i]^0，大部分实现也会得到 1，结果说不定也是对的。但明确写出来，既免疫了语言差异，也让读代码的人一眼就看懂你的意图。

5. 赛后的延伸思考：变体与下一步

5.1 换作区间连乘还能不能用前缀和？

打比赛最大的收获，不只是会做这一道题，而是把一道题吃透之后能秒掉一片同类题。赛后我习惯性地把“区间次方和”往周边变体上想了一遍，第一个想到的就是“区间连乘”。

给定一个静态数组，多次查询区间内所有元素的乘积，要取模。这个问题能不能用前缀和思路？不能直接用前缀和做除法式的撤销，因为当模数是素数时，可以用乘法逆元：

prod(l, r) = prefix_prod[r] * inv(prefix_prod[l-1]) % MOD

其中 prefix_prod[i] 表示前 i 个数的乘积取模，inv 表示模 MOD 下的乘法逆元。这和前缀和的减法对应，本质上也是一种“累积信息、差分撤销”的思想。如果你把这道区间次方和完全吃透了，这个变体对你来说也就是几分钟的事。

5.2 如果 p 的范围不再受限，前缀表会失效吗

这是评论区里问得最多的问题。如果把 p 的范围扩大到 1e5，甚至每次查询的 p 都不同，那我们的 5 行前缀表就直接失效了，因为你不能为 1e5 种情况各建一张表。

那怎么办？首先想清楚：p 既然很大，就不可能用 O(1) 查询直接出答案，复杂度需要重新平衡。一个常见套路是离线处理：把所有查询按 p 排序，离线操作。对于相同的 p，可以一次性建立这组查询要用的次方数组，例如先对数组里所有元素求 p 次方，再做一次前缀和，然后统一回答所有 p 相同的查询。这样复杂度是“不同的 p 的种数”乘以“n”，如果不同 p 的数量是 m，总复杂度大约是 O(m * n + q)。当 m 小于 1e5 量级时，这仍然是可接受的。更进一步，还可以用莫队来维护每种次方的桶，代价是复杂度更高，思路也更绕。

这种“静态区间 + 查询参数变化”的问题，本质上就是空间和时间权衡的艺术。你选择的方案必须依赖题目的数据范围来定，这也是为什么我总强调“看数据范围再说解法”。一个 1e5 的数据范围下 p 仍然只有 5，出题人摆明了是让你枚举维度，千万别把简单问题复杂化。

5.3 这题对周赛刷题习惯的三点提醒

借着 Round 135 的这道题，也顺便说说我对周赛刷题的三点体会。第一，拿到题先看数据范围，再想算法，顺序反了很容易写出一个“理论上正确但实际上超时”的代码。第二，对于静态数组的区间查询，优先想前缀和、差分、离线，而不是条件反射地上线段树、树状数组，“工具越重型，思考越稀薄”。第三，赛后别急着走，把每道题的正解思路和别人的优秀代码都看一遍，很多所谓的“难题”破绽就在别人的代码注释里写着。

我打牛客周赛这么多次，最大的感受就是：这赛事的题目质量整体在线，尤其是中间档位这几道题，非常能训练思维的灵活度。Round 135 的区间次方和虽然整体难度不高，但踩坑的点特别典型，很值得记一轮。下次如果数据里再看到“小范围参数”，记得先停下来想想——它可能就是出题人留给你的那扇门。