lessons/课程/08-高级线段树与树状数组/01-Fenwick离线计数与序关系.md

Fenwick 进阶：把值域顺序变成前缀计数

本节目标

在已掌握树状数组单点加、前缀和的基础上，学会把三元关系、左右频次关系和带负数子段和统一改写成“扫描线 + 已处理集合中的秩查询”。

前置知识与课前自测

前置：Fenwick Tree、离散化、前缀和。

1. 若值域到 $10^9$，树状数组下标应怎样得到？
2. 严格小于 $x$ 与小于等于 $x$ 在 lower_bound/upper_bound 中分别怎样表达？
3. 统计三元组时固定中点，左右两侧能否独立计数再相乘？需要什么条件？

答案

1. 对所有可能被查询/更新的值排序去重，使用秩。 2. `

问题动机与核心知识

Fenwick 真正擅长的不是“数组”，而是动态维护一个有序多重集的前缀计数。典型流程：

1. 选择扫描方向，使一侧对象已经进入数据结构；
2. 把关系改写成 <rank、<=rank 或总数减前缀；
3. 查询当前贡献，再把当前对象加入或移出；
4. 对严格不等号单独核对重复值。

实现指南

add(rank,+1) 与 sum(rank) 中秩统一为 1-based。答案的配对数可达 $O(n^2)$ 或 $O(n^3)$，必须用 long long。离散化只保持比较顺序，不会保持差值；需要做加减阈值时，应在原始前缀和值上二分，而不是在秩上直接减。

精选例题 1：Enemy is weak

来源与题意

• CodeForces-61E Enemy is weak，难度 1900，Codeforces Beta Round 57
• $n\le10^6$，所有 $a_i$ 互异；统计 $ia_j>a_k$。
Hint 1
固定中点 $j$。
Hint 2
贡献为“左侧比它大”乘“右侧比它小”。
Hint 3
两次相反方向扫描分别求这两个数组。

Observations

• $O(n^3)$ 的选择顺序中，固定 $j$ 后左右条件不再互相影响。
• 每个三元组只有一个中点，因此乘积求和不会重复。
• 值互异让 < 与 <= 的边界简单；若允许重复，必须仍使用严格秩查询。

Editorial

离散化权值。左到右扫描：结构中存下标小于 $j$ 的值，left_greater[j]=(j-1)-count(<=a_j)。右到左扫描得到 right_smaller[j]=count(<a_j)。答案为两者乘积之和。

正确性证明

对固定 $j$，每个满足 $a_i>a_j$ 的左下标和每个满足 $a_k<a_j$ 的右下标能且只能组合成一个合法三元组；反之合法三元组必被其中点项计入。对全部 $j$ 求和覆盖且不重。

复杂度 $O(n\log n)$、空间 $O(n)$，能承受 $10^6$。

核心伪代码与附件

rank = coordinate_compress(a)
scan left -> right to compute left_greater[j]
clear Fenwick
scan right -> left to compute right_smaller[j]
answer = sum(left_greater[j] * right_smaller[j])

完整 C++17 附件

精选例题 2：Pashmak and Parmida's problem

来源与题意

• CodeForces-459D Pashmak and Parmida's problem，难度 1800
• $n\le10^6$；令 $L_i$ 为 $a_i$ 在前缀 $[1,i]$ 的出现次数，$R_j$ 为 $a_j$ 在后缀 $[j,n]$ 的出现次数，统计 $iR_j$。
Hint 1
预处理所有 $L_i,R_i$。
Hint 2
扫描 $i$ 时，Fenwick 中只保留下标 $j>i$ 的 $R_j$。

Observations

• 比较对象不再是原值，而是两个位置相关的频次数组。
• R_j 范围仅为 $1..n$，不需对原值做值域树。
• 查询前先移除当前位置的 $R_i$，才能严格保证 $i<j$。

Editorial 与证明

哈希/排序预处理左右频次。Fenwick 初始加入全部 $R_j$；从左到右，对当前位置先删除 $R_i$，再查询 <L_i 的剩余个数。结构中恰是所有 $j>i$，查询条件恰是 $R_j<L_i$，故每个目标对在其左端点处理时计一次。复杂度 $O(n\log n)$。

核心伪代码与附件

L = prefix_occurrence_number(a)
R = suffix_occurrence_number(a)
Fenwick.add(R[j], 1) for all j
for i from 1 to n:
    Fenwick.add(R[i], -1)
    answer += Fenwick.sum(L[i] - 1)

完整 C++17 附件

精选例题 3：Petya and Array

来源与题意

• CodeForces-1042D Petya and Array，难度 1800
• $n\le2\times10^5$，元素可正可负，$|t|\le2\times10^{14}$；统计和严格小于 $t$ 的非空子段。
Hint 1

子段 $[l,r]$ 对应前缀对 $P_r-P_{l-1}

Hint 2

改写为此前前缀 $P_{l-1}>P_r-t$。

Observations

• 负数使双指针失去单调性，但前缀对的不等式仍成立。
• 查询阈值 $P_r-t$ 未必出现在离散化集合中，应在原前缀数组上 upper_bound。
• 空前缀 $P_0=0$ 必须先加入结构，否则漏掉从 1 开始的子段。

Editorial 与正确性证明

依次处理右端点 $r$。Fenwick 存所有此前前缀和；查询其中严格大于 $P_r-t$ 的数量，再加入 $P_r$。每个此前前缀唯一对应一个 $l-1$，不等式与子段条件等价，所以计数充要且不重复。复杂度 $O(n\log n)$，前缀和与答案均用 64 位。

核心伪代码与附件

prefix[0] = 0; prefix[i] = prefix[i-1] + a[i]
coordinates = sorted_unique(prefix)
Fenwick.add(rank(prefix[0]), 1)
for r in 1..n:
    le = number of inserted prefixes <= prefix[r] - t
    answer += inserted_count - le
    Fenwick.add(rank(prefix[r]), 1)

完整 C++17 附件

扩展与联系

二维偏序常由排序固定一维、Fenwick 维护另一维；若还多一维，可能进入 CDQ 分治。Fenwick 的限制是合并信息必须可做前缀差或单调选择，任意区间复杂结构仍需线段树。

总结与自检

1. 三题中 Fenwick 下标分别代表什么？
2. 哪一步保证位置关系严格成立？
3. 前缀和题为何用 upper_bound(P_r-t)？
4. 何时能固定中点把左右计数相乘？

课后训练建议

先用 $O(n^3)/O(n^2)$ 暴力对拍三题；每次写 Fenwick 前先用一句中文写明“结构中当前有哪些对象”。若这句随扫描位置不成立，代码通常也会错。