前缀和擅长把一个区间写成两个前缀的差；线段树擅长合并两个子区间的摘要。但如果查询要求“每个值的出现次数先平方，再乘这个值”，一个总和就不够合并了。

这篇接在前缀和与差分、树状数组与序列计数之后，换一种复用方式：允许重排查询时，不必独立计算每个区间，可以把上一个区间的统计挪到下一个区间。这就是本篇的莫队算法。

官方题目与约束

题目为 Codeforces 86D Powerful array。官方页面核对日期为 2026-10-05；以下是中文概括，推导与示例为本站原创。

项目 官方信息
难度 2200
标签 data structures、implementation、math、two pointers
数组长度 n 与查询数 q 均为 1 到 200000；原题将查询数写作 t
元素范围 1 到 1000000
查询 1 ≤ l ≤ r ≤ n，数组没有修改
目标 对每个区间计算所有值 x 的 x × cnt[x]² 之和

这里的 cnt[x] 只统计当前查询区间。值没有出现时贡献为 0；输出必须保持输入查询的顺序。

朴素扫描为什么重复太多

独立扫描每个查询区间，最坏需要 O(nq) 次访问。即使频次数组清零很快，大区间之间相同的元素仍被反复统计。

普通前缀总和也不能直接相减得到答案。设某个值 x 在两个不相交片段中分别出现 a 次、b 次，合并后的贡献是 x(a+b)²，比两个片段贡献之和多出 2xab。若节点只保存一个总答案，这个交叉项就无从计算。

这不是说线段树绝对无法处理任何频次问题，而是说本题没有从上述标量摘要直接得到常数时间合并规则。莫队选择保留整张当前频次表，只要求边界上的一个元素能快速加入和移除。

方法 保存的信息 本题遇到的限制
独立扫描 每个查询重新统计 大量重叠区间重复工作
一个前缀答案 每个前缀的频次平方和 相减缺少交叉项
只有总答案的区间节点 每段一个数 不知道相同值在两边的频次
离线移动窗口 当前区间的完整频次表 需要可重排查询和廉价增删

加入和删除的两个差分公式

维护闭区间 [L,R]、频次数组 cnt 和答案 power。加入的值为 x，加入前 cnt[x]=c，则贡献变化为：

x × ((c+1)²-c²) = x × (2c+1)。

删除时，删除前 cnt[x]=c，贡献减少：

x × (c²-(c-1)²) = x × (2c-1)。

两式的 c 都是操作之前的频次。先改频次再套旧公式，是最常见的差一错误。其他值的频次没有变化，所以不必重算它们的贡献。

操作 操作前 c 答案变化 操作后频次
加入第一个 3 0 +3 1
再加入一个 3 1 +9 2
再加入一个 3 2 +15 3
删除一个 3 3 −15 2

前三次增量总和 3+9+15=27，恰为 3×3²。删除必须针对当前窗口中真实存在的位置，不能让频次变成负数。

为什么先扩张窗口再收缩

初始窗口设为 L=1、R=0，表示空区间，全部频次与 power 为 0。对于目标 [l,r]，按下面次序移动：

  1. L>l 时，先把 L 减一，再加入新位置。
  2. R<r 时，先把 R 加一，再加入新位置。
  3. L<l 时，删除 L 位置，再把 L 加一。
  4. R>r 时，删除 R 位置，再把 R 减一。

先扩张会暂时覆盖旧区间和目标区间，然后才删除目标以外的端点。这样即使两个查询完全不相交，也不会对一个尚未加入的位置执行删除。空区间起步时也可使用同一套顺序。

用原创数组 [1,2,1,3,2]，从 [1,3] 移到 [2,5]：

步骤 当前区间 cnt[1], cnt[2], cnt[3] power
起点 [1,3] 2,1,0 6
加入位置 4 的 3 [1,4] 2,1,1 9
加入位置 5 的 2 [1,5] 2,2,1 15
删除位置 1 的 1 [2,5] 1,2,1 12

最终可独立检查：1×1²+2×2²+3×1²=12。注意加入第二个 2 只增加 6，不是把新的完整贡献 8 再加一遍。

分块排序让窗口少走一些路

仅仅可以移动窗口，还不保证快。若输入查询反复在数组两端跳跃，直接按输入顺序执行，仍可能达到 O(nq)。

取块长 B，将查询按左端点所属块 (l-1)/B 分组。先按块编号递增；同一块内，偶数块按右端点递增，奇数块按右端点递减。这种蛇形顺序减少相邻块之间右端点回到起点的折返，但它不保证全局最短移动路线。

原查询编号 区间 B=2 时左端块编号 排序位置
0 [4,5] 1 3
1 [1,3] 0 1
2 [2,5] 0 2
3 [3,3] 1 4

排序后先处理 [1,3]、[2,5]，再处理 [4,5]、[3,3]。但是答案写入 answer[原查询编号]，因此最终仍按 0、1、2、3 输出。对上面的五元素数组，输出应为 5、6、12、1。

正确性证明

窗口不变量。 每次边界操作结束后，cnt[x] 等于当前 [L,R] 内 x 的出现次数，power 等于这些频次的加权平方和。

初始空区间满足不变量。加入位置时，仅对应值 x 的次数从 c 变成 c+1，增量公式精确补上新旧贡献之差；删除同理。边界变化与加入、删除的位置一致，所以归纳可知不变量始终成立。

查询正确性。 四个 while 循环结束后 L=l 且 R=r，窗口不变量立即给出当前查询所需答案。先扩张后收缩保证删除的位置属于窗口，因此证明中的删除前提成立。

重排不改变题意。 数组是静态的，各查询互不依赖。离线排序只改变求值顺序；原编号提供排序前后的对应关系，所以每个输出位置仍得到原查询的正确答案。若后续查询依赖前一个答案解密，就不能直接这样离线重排。

复杂度与整数范围

同一个左端块内，L 每次变化不超过 O(B)，累计 O(qB)。跨块时左端块单调前进，总跨块代价为 O(n)。每块中的 R 单调移动，代价 O(n)；最多 O(n/B) 块，因此右端总移动 O(n²/B+n)。

总时间为 O(q log q + qB + n²/B + n)，每次增删 O(1)。本实现取 B=max(1,floor(sqrt(n)))，得到常见的 O(q log q + (n+q)sqrt(n)) 上界。如果 n、q 差别很大，可以围绕 n/sqrt(q) 选择块长并实测常数，但不能省掉正确性与边界检查。

频次表按最大值 V 直接开数组，空间为 O(n+q+V)。本题 V≤10⁶；若推广到大值域，可以离散化索引，但权重必须保留原值，不能把原值 x 换成压缩编号。

答案上界为 10⁶ × n² ≤ 4×10¹⁶：因为所有频次非负，频次平方和不超过频次和的平方。long long 足够，int 不够。增量乘法也要在 64 位中完成，不能只把最终结果变量改成 64 位。

完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

struct Query {
    int l, r, id, block;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    int maximum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        maximum = max(maximum, a[i]);
    }
    const int blockSize = max(1, static_cast<int>(sqrt(n)));
    vector<Query> queries(q);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        queries[i] = {l, r, i, (l - 1) / blockSize};
    }
    sort(queries.begin(), queries.end(), [](const Query& x, const Query& y) {
        if (x.block != y.block) return x.block < y.block;
        if (x.r != y.r) {
            return (x.block & 1) ? x.r > y.r : x.r < y.r;
        }
        return x.id < y.id;
    });

    vector<int> count(maximum + 1, 0);
    vector<long long> answer(q);
    long long power = 0;
    auto add = [&](int position) {
        const int x = a[position];
        power += (2LL * count[x] + 1) * x;
        ++count[x];
    };
    auto remove = [&](int position) {
        const int x = a[position];
        power -= (2LL * count[x] - 1) * x;
        --count[x];
    };

    int left = 1, right = 0;
    for (const Query& query : queries) {
        while (left > query.l) add(--left);
        while (right < query.r) add(++right);
        while (left < query.l) remove(left++);
        while (right > query.r) remove(right--);
        answer[query.id] = power;
    }
    for (long long value : answer) cout << value << '\n';
}

边界与错误清单

情况或错误 应检查什么
n=1，单点查询 第一个元素从频次 0 正确加入
全部值相同 长度 m 的答案是 x×m²，而不是 x×m
所有值互异 平方均为 1，答案退化为普通区间和
多次重复同一区间 不需要移动，结果应完全一致
不相交区间 扩张在前，不能删掉尚未加入的位置
反复进入和离开同一值 增删公式使用操作前频次
相同右端点 比较器必须满足严格弱序，不能写成 ≤
离线排序之后 用 id 还原，不按处理顺序输出
长区间和大值 用 64 位计算每一个乘法

本站测试提取本文代码编译，使用独立的区间频次重算进行小数组穷举与随机对拍；大规模同值、互异与周期数组则使用独立计数公式核验。它检查代码与推导是否一致，不冒充官方在线评测提交记录。

什么时候选择莫队

当数组静态、查询可离线、窗口单点增删便宜，而区间摘要又不容易快速合并时，莫队是值得考虑的方法。普通区间和已有 O(1) 前缀查询，就没必要退回 O(sqrt(n)) 量级的移动。

读完后可以回到线段树三题，比较两种问题：一个问“两个摘要能否合并”，另一个问“边界移动一步能否更新”。选择数据结构之前，先明确你真正拥有的局部操作。