“有多少对”“有多少组三元组”看起来需要多重循环，但很多位置限制可以由扫描方向自动保证，剩下的只是一个动态前缀计数问题。另一类题甚至不需要维护完整计数：如果只问奇偶性，就应先研究操作如何改变奇偶性。

这篇从 前缀和与差分 接出一条序列计数支线：扫描保证位置关系，树状数组回答大小关系，不变量决定哪些状态根本不用保存。

1. 学习路线与官方约束

题名、难度、标签与约束于 2026-09-28 核对 Codeforces 官方题目页。下面的说明是重新组织的题意，不替代原题。

官方题目 难度 官方标签 本文的切入点
459D · Pashmak and Parmida’s problem 1800 data structures, divide and conquer, sortings 先预处理频次，再扫描频次的分布
61E · Enemy is weak 1900 data structures, trees 固定中间位置，把三元组拆成左右选择
911D · Inversion Counting 1800 brute force, math 初始计数可以用树状数组，后续只更新奇偶性
题目 数据边界 时间 / 空间限制 会影响实现的条件
459D 1 ≤ n ≤ 10^6，1 ≤ a[i] ≤ 10^9 3 秒 / 256 MB 数值可以重复，答案可能超过 32 位
61E 3 ≤ n ≤ 10^6，1 ≤ a[i] ≤ 10^9 5 秒 / 256 MB 所有数值互不相同，三元组数须用 64 位
911D 1 ≤ n ≤ 1500，1 ≤ m ≤ 2×10^5 2 秒 / 256 MB 初始数组是 1..n 的排列，反转操作依次累积

建议先手算一遍第二节的树状数组，再做 459D；61E 用来练习“枚举中间”，911D 用来提醒自己：有数据结构也不意味着每次操作都需要它。

2. 树状数组：动态维护一个计数前缀

从静态前缀和到动态前缀和

假设 freq[x] 表示已扫描元素中数值为 x 的数量。查询“小于 x 的元素数”等于 freq[1]+...+freq[x-1]。

普通前缀和查询很快，但插入一个元素就可能需要修改后面所有前缀。树状数组（Fenwick tree）把前缀拆成若干二进制长度的块：单点增加和前缀求和都只需 O(log n)。

令 lowbit(x) = x & -x。使用从 1 开始的下标，tree[x] 保存区间 [x-lowbit(x)+1, x] 的总和。

节点 x lowbit(x) 保存的区间
1 1 [1,1]
4 4 [1,4]
6 2 [5,6]
7 1 [7,7]
8 8 [1,8]

查询 sum(7) 时，依次访问 7、6、4，拼出 [7,7] + [5,6] + [1,4]，既不漏项也不重叠。每次减去 lowbit，会清除当前最低的一个二进制 1，因此步数不超过二进制位数。

在长度 8 的树中给位置 3 加一，依次更新 3、4、8。这些正是沿树状数组祖先链覆盖位置 3 的块；跳转 x += lowbit(x) 越过不包含该位置的块，从而保持每个节点的区间和定义。

离散化不是改变比较关系

值域到 10^9，不能直接开这么大的计数数组。把原数组复制、排序、去重，再把每个数替换成从 1 开始的排名：相等仍相等，大小次序不变。比如 [100,7,100,42] 变成 [3,1,3,2]。

想查询什么 已插入数量为 seen 时的公式 等号在哪一边
严格小于 x sum(x-1) 不包含 x
小于等于 x sum(x) 包含 x
严格大于 x seen-sum(x) 扣掉小于等于 x
大于等于 x seen-sum(x-1) 只扣掉严格小于 x

sum(0)=0 是合法空前缀；add(0,1) 则会永远停在 0。离散化排名必须加一。三份代码都保留完整的树状数组定义，便于分别提交。

3. 第一题：459D Pashmak and Parmida’s problem

把两段频率变成两个数组

定义 L[i] 为 a[i] 在 [1,i] 中的出现次数，R[i] 为 a[i] 在 [i,n] 中的出现次数。目标是统计 i<j 且 L[i]>R[j] 的点对。

直接枚举所有 (i,j) 即使预处理了 L、R，仍需 O(n²)。注意第二个条件比较的是出现次数，不是 a[i] 与 a[j] 的大小。原数值只负责确定哪些位置属于同一种值。

用数组 [1,2,1,1,2,2,1] 手算：

位置（1 起） 1 2 3 4 5 6 7
a 1 2 1 1 2 2 1
L 1 1 2 3 2 3 4
R 4 3 3 2 2 1 1

从右向左，让位置条件自动成立

处理 i 之前，树状数组只存所有 j>i 的 R[j]。因此当前贡献就是 sum(L[i]-1)；查询之后才加入 R[i]。

扫描 i 右侧已插入的 R（按位置列出） 小于 L[i] 的数量 累计答案
7 空 0 0
6 1 1 1
5 1,1 2 3
4 2,1,1 3 6
3 2,2,1,1 2 8
2 3,2,2,1,1 0 8
1 3,3,2,2,1,1 0 8

正确性可用归纳说明：最右位置处理前树为空，与“只含右侧”一致；查询准确统计全部合法右端点；插入当前 R 后，恰好形成下一个位置的右侧集合。每一对合法 (i,j) 只在处理 i 时计入一次。

完整 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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Fenwick {
    int n;
    vector<int> tree;
    explicit Fenwick(int size) : n(size), tree(size + 1, 0) {}
    void add(int x, int delta) {
        for (; x <= n; x += x & -x) tree[x] += delta;
    }
    int sum(int x) const {
        int result = 0;
        for (; x > 0; x -= x & -x) result += tree[x];
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    vector<int> values = a;
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    for (int& x : a) {
        x = static_cast<int>(lower_bound(values.begin(), values.end(), x)
                             - values.begin()) + 1;
    }
    vector<int> count(values.size() + 1, 0), left(n), right(n);
    for (int i = 0; i < n; ++i) left[i] = ++count[a[i]];
    fill(count.begin(), count.end(), 0);
    for (int i = n - 1; i >= 0; --i) right[i] = ++count[a[i]];

    Fenwick bit(n); // Its coordinate is frequency, not the original value.
    long long answer = 0;
    for (int i = n - 1; i >= 0; --i) {
        answer += bit.sum(left[i] - 1);
        bit.add(right[i], 1);
    }
    cout << answer << '\n';
}

排序、二分映射和树状数组扫描总时间 O(n log n)，额外空间 O(n)。树节点只存不超过 n 的元素数量，用 int 足够；答案不超过 n(n-1)/2，用 long long。

边界 应有结果或性质 能抓住的错误
n=1 0 把当前位置提前插入
所有值不同 L、R 都是 1，答案 0 把严格大于写成大于等于
三个相同值 只有 (2,3)，答案 1 比较原数值而不是频次
百万个相同值 floor((n-1)²/4) 32 位答案溢出

最后一个公式来自 L[i]=i、R[j]=n-j+1，合法条件为 i<j 且 i+j>n+1；按 j 对 max(0,2j-n-2) 求和即可得到该闭式。

4. 第二题：61E Enemy is weak

固定中间项，让两个选择独立

要统计 i<j<k 且 a[i]>a[j]>a[k]。三重枚举是 O(n³)；即使固定 j 后分别线性扫描左右，也要 O(n²)。

定义 greaterLeft[j] 为左边严格较大元素数，smallerRight[j] 为右边严格较小元素数。固定 j 后，任何一个合法左端点与任何一个合法右端点组合都会满足条件，所以贡献为两者乘积。

对 [10,8,3,1]：

中间位置 j a[j] 左侧较大数 右侧较小数 贡献
1 10 0 3 0
2 8 1 2 2
3 3 2 1 2
4 1 3 0 0

答案为 4。每个三元组有唯一中间位置，因此求和不会重复。

两遍扫描的循环不变量

正向扫描到零起下标 j 时，树中有 j 个先前元素；j-sum(rank[j]) 就是左侧严格较大数。清空计数状态、重新建立一棵树后反向扫描，sum(rank[j]-1) 给出右侧严格较小数。两遍都先查询、后插入。

这并不是把整个数组排序后数三元组。排序的只是辅助映射表，原位置顺序不能改变。两遍树状数组分别保证左右位置关系，排名查询保证值的大小关系，乘法原理与唯一中间点共同给出正确性。

完整 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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Fenwick {
    int n;
    vector<int> tree;
    explicit Fenwick(int size) : n(size), tree(size + 1, 0) {}
    void add(int x) {
        for (; x <= n; x += x & -x) ++tree[x];
    }
    int sum(int x) const {
        int result = 0;
        for (; x > 0; x -= x & -x) result += tree[x];
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    vector<int> values = a;
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    for (int& x : a) {
        x = static_cast<int>(lower_bound(values.begin(), values.end(), x)
                             - values.begin()) + 1;
    }
    Fenwick leftBit(static_cast<int>(values.size()));
    vector<int> greaterLeft(n);
    for (int j = 0; j < n; ++j) {
        greaterLeft[j] = j - leftBit.sum(a[j]);
        leftBit.add(a[j]);
    }
    Fenwick rightBit(static_cast<int>(values.size()));
    long long answer = 0;
    for (int j = n - 1; j >= 0; --j) {
        int smallerRight = rightBit.sum(a[j] - 1);
        answer += 1LL * greaterLeft[j] * smallerRight;
        rightBit.add(a[j]);
    }
    cout << answer << '\n';
}

时间 O(n log n)，空间 O(n)。1LL 必须在乘法之前参与运算，而不是让两个 int 先相乘、溢出后才赋给 long long。

输入形态 答案 检查重点
严格递增 0 不等号方向
三个数严格递减 1 中间位置是否计入自身
n 个数严格递减 n(n-1)(n-2)/6 三元组上界
n=1,000,000 严格递减 166,666,166,667,000,000 既超过 32 位，也超过 JavaScript Number 精确整数范围

独立验证器用 JavaScript BigInt 计算最后一行的期望值，避免让测试程序自身的精度问题掩盖错误。题目保证数值互异；代码仍使用严格比较的标准写法，不把互异条件当成省略等号分析的借口。

5. 第三题：911D Inversion Counting

不要维护题目没有询问的信息

逆序对是 i<j 且 a[i]>a[j] 的点对。每次反转 [l,r] 后，题目只问逆序对数是奇数还是偶数。

直接反转数组、重算逆序数，即使每次计数用树状数组也要 O(m n log n)。只保留一个奇偶位，才能充分利用问题结构。

初始奇偶性可以用 O(n²) 暴力求出：n 仅为 1500，这已经足够。下面使用树状数组统一前两题的知识，初始为 O(n log n)；真正关键不是这点优化，而是之后每次只需 O(1)。

一次反转为什么只看长度

令区间长度 len=r-l+1，把所有数对分成三类。

数对位置 反转的影响 对总奇偶性的影响
两个都在区间外 位置与数值均未变 无
一个在区间内、一个在区间外 区间内数值集合不变，外部元素仍全部在它们左侧或右侧 与该外部元素有关的逆序对总数不变
两个都在区间内 相对先后顺序颠倒，且数值不同 每一对的逆序状态翻转

区间内共有 len(len-1)/2 对。某一对从 0 变 1 或从 1 变 0，对模 2 的计数都是翻转。因此新奇偶性等于旧奇偶性异或 C(len,2) mod 2。

互异条件非常重要：[1,1] 反转后仍无逆序对，不能套用“长度 2 必翻转”。本题是排列，而且反转保持排列性质，所以每轮证明都继续成立。

len mod 4 C(len,2) 的奇偶 是否翻转答案
0 偶 否
1 偶 否
2 奇 是
3 奇 是

累积操作的手算

从 [1,2,4,3] 开始，逆序数为 1。下面为了验证推导才列出实际数组；正式程序不需要真的反转。

操作 实际数组 逆序数 仅用奇偶位得到的输出
反转 [1,1] [1,2,4,3] 1 odd
反转 [1,4] [3,4,2,1] 5 odd
再反转 [1,4] [1,2,4,3] 1 odd
反转 [2,3] [1,4,2,3] 2 even

完整 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
#include <iostream>
#include <vector>
using namespace std;

struct Fenwick {
    int n;
    vector<int> tree;
    explicit Fenwick(int size) : n(size), tree(size + 1, 0) {}
    void add(int x) {
        for (; x <= n; x += x & -x) ++tree[x];
    }
    int sum(int x) const {
        int result = 0;
        for (; x > 0; x -= x & -x) result += tree[x];
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    Fenwick bit(n); // Input is a permutation of 1..n.
    int parity = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        parity ^= (i - bit.sum(x)) & 1;
        bit.add(x);
    }
    int m;
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        long long len = r - l + 1;
        parity ^= static_cast<int>((len * (len - 1) / 2) & 1LL);
        cout << (parity ? "odd" : "even") << '\n';
    }
}

总时间 O(n log n + m)，额外空间 O(n)。读完初始数组后，树状数组不再使用，也不需要修改其中的信息；它完成的任务只是产生初始奇偶位。

6. 三题一起复盘：到底在树里存什么

问题 树的坐标轴 节点累计内容 算法真正依赖的不变量
459D 出现次数 1..n 右侧有多少个 R 落在该范围 查询前只含严格右侧位置
61E 数值的离散化排名 已扫描元素的数量 正向只有左侧，反向只有右侧
911D 初始阶段 排列值 1..n 先前元素的数量 每对逆序在其右端点被计入
911D 查询阶段 不再需要树 一个奇偶位 反转影响的奇偶只由长度决定
常见错误 为什么错 最小修正
把 459D 的原数值作为查询阈值 题目比较的是频次 分开值的排名与出现次数
查询之前先插入当前位置 扫描集合可能包含自己 明确循环入口的不变量
把 <x 写成 sum(x) 多计等值项 严格小于用 sum(x-1)
两遍扫描共用未重置的树 左侧数据污染右侧统计 建立一棵新的空树
将原数组整体排序后计数 丢失位置条件 只排序辅助映射数组
用 int 保存三元组答案 大输入溢出 乘法起点和答案均使用 64 位
911D 每次从初始奇偶重新算 操作是累计的 始终更新当前 parity
把排列证明套到重复值数组 相等数对不翻转逆序状态 检查证明用到的条件

能否说清“坐标轴是什么”，通常比能否背出 lowbit 更能判断是否理解了树状数组。需要更复杂的区间摘要时，再读 线段树三题；只有加法计数与前缀查询时，树状数组通常更轻巧。

7. 可复现的独立验证

验证程序在 tests/verify-fenwick-three-article.cjs，直接从本文提取三份 C++，使用 g++ -std=c++17 -O2 -Wall -Wextra -pedantic 编译，要求无警告。它不复用正文算法作为参考答案：

  • 459D：直接枚举位置对，逐段统计相应数值出现次数；另枚举三值小数组并加入高值随机数据。
  • 61E：小数据直接枚举所有三元组；百万长度递减数组用 BigInt 的组合数独立核验。
  • 911D：对小排列真实执行每次反转，再用双循环重算逆序对；覆盖连续反转和单点区间，另测 20 万次查询。
  • 三题都保留官方样例与本文手算，检查小边界、最大规模和输出格式。

在项目根目录执行：

1
node tests/verify-fenwick-three-article.cjs

编译产物保留在验证目录，脚本不清理缓存或构建目录。测试能增加实现的可信度，但扫描不变量、乘法计数和反转奇偶性的证明仍是算法成立的依据。