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 附件

扩展与联系

高阶例题：Inversions

来源信息与题意

• VJudge：AtCoder-agc023_e Inversions
• 原题：AtCoder Grand Contest 023 E
• 难度：AGC 1700 分；考点：受限排列计数、交换配对、零因子分段、Fenwick

给定 $1\le N\le2\times10^5$ 与 $1\le A_i\le N$。对每个满足 $P_i\le A_i$ 的 $1..N$ 排列 $P$，计算其逆序数；求所有合法排列逆序数之和，模 $10^9+7$。

Hint 1：先数合法排列

按数值从 $N$ 到 1 放置。放值 $x$ 时，可用位置数为 $$ c_x=\#\{i:A_i\ge x\}-(N-x). $$

Hint 2：固定位置对，不要固定实际取值

对 $i

Hint 3：把较大上界降到较小上界

若 $A_i\le A_j$，额外要求 $P_j\le A_i$，就等价于把第 $j$ 个上界从 $A_j$ 降到 $A_i$。此时交换两个位置仍合法，逆序恰占一半。

Hint 4：上界下降后，排列数怎样变化

把一个上界从 $v$ 降到 $u\le v$，每个 $x\in(u,v]$ 的可选位置数从 $c_x$ 变成 $c_x-1$，所以计数比为 $$ R(u,v)=\prod_{x=u+1}^{v}\frac{c_x-1}{c_x}. $$ 若区间含 $c_x=1$，该比值就是 0，不能直接用逆元。

Hint 5：Fenwick 维护什么

令 $Q_t=\prod_{x=1}^{t}(c_x-1)/c_x$，但按 $c_x=1$ 切段。扫描位置 $j$ 时，按此前的上界 $A_i$ 查询 $Q_{A_j}/Q_{A_i}$ 或其反向形式。

Observations

1. 枚举排列完全不可行；按值从大到小放置后，合法排列总数分解成独立乘积 $T=\prod_x c_x$。若某个 $c_x\le0$，不存在合法排列，答案立即为 0。
2. 线性期望虽能把答案写成 $T\sum_{iP_j)$，但直接求两个位置的联合分布仍有 $O(N^2)$ 个状态。交换位置把概率问题改成“再收紧一个上界后的排列数”。
3. 若 $u=A_i\le v=A_j$，收紧 $j$ 的上界到 $u$ 后，每个排列与交换 $i,j$ 后的排列配对，二者恰有一个逆序。因此该位置对贡献 $T\,R(u,v)/2$。
4. 若 $u>v$，同理配对“不构成逆序”的排列，故贡献为 $T-T\,R(v,u)/2$。这解释了为什么先统计 $A$ 自身的逆序数，再加一正一负两类修正。
5. 比值乘积含零时贡献应为 0。按前缀中 c_x==1 的出现次数分组，只有两上界位于同一组时才能用前缀乘积相除；这一步避免了对 0 求模逆。

Editorial 与正确性证明

先计算全部 $c_x$ 与 $T=\prod c_x$。对任意 $u\le v$，把某个上界 $v$ 改为 $u$：对值 $x\in(u,v]$，该位置不再可选，所以降序放置时选择数由 $c_x$ 变为 $c_x-1$；其他值不变。因此新排列数确为 $T R(u,v)$。

固定 $iP_j$，贡献为 $TR/2$。若 $A_i>A_j$，完全相同的对合证明“不逆序”数为 $TR/2$，故逆序数为 $T-TR/2$。这覆盖每个位置对且每个排列逆序恰按其位置对计一次。

为在 $O(N\log N)$ 汇总，令

$$ Qt=\prod{1\le x\le t,\ c_x\ne1}\frac{c_x-1}{c_x}. $$

在不跨越 c_x==1 的同一组内，$R(u,v)=Q_v/Q_u$。从左到右扫描当前上界 $v=A_j$，三个 Fenwick 分别维护此前上界的数量、$Q_u$ 之和与 $Q_u^{-1}$ 之和：

• 数量树给出 $u>v$ 的对数，贡献基础项 $T$；
• $u\le v$ 时累加 $Q_v/Q_u$；
• $u>v$ 时减去 $Q_u/Q_v$；
• 查询范围限制在 $v$ 所在的同一零因子组，跨组比值本来就是 0。

最后把正负修正乘 $T/2$。预处理与扫描均为 $O(N\log N)$，空间 $O(N)$，能通过 $N=2\times10^5$。

核心伪代码与参考实现附件

for x from N down to 1:
    c[x] = count(A[i] >= x) - (N-x)
    if c[x] <= 0: return 0
T = product(c[x])

build Q[x] from factors (c[x]-1)/c[x]
split value axis after every x with c[x] == 1

for v in A from left to right:
    base_inversions += count_of_inserted_values_greater_than(v)
    correction += Q[v] * sum(1/Q[u]) for inserted u <= v in same group
    correction -= (1/Q[v]) * sum(Q[u]) for inserted u > v in same group
    insert v into the three Fenwick trees

answer = T * base_inversions + T/2 * correction

完整 GNU C++17 参考实现：AtCoder-agc023_e.cpp

实现细节、复盘与变式

• c_x 是整数选择数，不是模数意义下的值；必须先用整数判断是否为 0。
• 因为 $1\le c_x\le N<10^9+7$，除 c_x-1=0 外都可安全求逆；零因子用分组处理。
• 相等上界 $u=v$ 时空乘积为 1，该位置对贡献 $T/2$，代码的闭区间查询必须包含相等值。
• 识别信号不是“求期望就结束”，而是“交换两个位置后约束何时仍合法”；对合把联合分布删成一次计数比值。
• 若约束改成位置允许任意集合而非前缀 $[1,A_i]$，收紧一个位置不再只让连续一段 $c_x$ 各减 1，乘积比与一维 Fenwick 都会失效。

扩展与联系

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

总结与自检

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

课后训练建议

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