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

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>答案</summary>

1. 对所有可能被查询/更新的值排序去重，使用秩。
2. `<x` 用 `lower_bound(x)` 之前的数量；`<=x` 用 `upper_bound(x)` 之前的数量。
3. 可以；每个合法左点与合法右点任意组合都唯一产生一个三元组。

</details>

## 问题动机与核心知识

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](https://vjudge.net/problem/CodeForces-61E)，难度 1900，Codeforces Beta Round 57
- $n\le10^6$，所有 $a_i$ 互异；统计 $i<j<k$ 且 $a_i>a_j>a_k$。

<details><summary>Hint 1</summary>固定中点 $j$。</details>
<details><summary>Hint 2</summary>贡献为“左侧比它大”乘“右侧比它小”。</details>
<details><summary>Hint 3</summary>两次相反方向扫描分别求这两个数组。</details>

### 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$。

### 核心伪代码与附件

```text
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 附件](../../参考实现/08-高级线段树与树状数组/CodeForces-61E.cpp)

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

### 来源与题意

- [CodeForces-459D Pashmak and Parmida's problem](https://vjudge.net/problem/CodeForces-459D)，难度 1800
- $n\le10^6$；令 $L_i$ 为 $a_i$ 在前缀 $[1,i]$ 的出现次数，$R_j$ 为 $a_j$ 在后缀 $[j,n]$ 的出现次数，统计 $i<j,L_i>R_j$。

<details><summary>Hint 1</summary>预处理所有 $L_i,R_i$。</details>
<details><summary>Hint 2</summary>扫描 $i$ 时，Fenwick 中只保留下标 $j>i$ 的 $R_j$。</details>

### 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)$。

### 核心伪代码与附件

```text
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 附件](../../参考实现/08-高级线段树与树状数组/CodeForces-459D.cpp)

## 精选例题 3：Petya and Array

### 来源与题意

- [CodeForces-1042D Petya and Array](https://vjudge.net/problem/CodeForces-1042D)，难度 1800
- $n\le2\times10^5$，元素可正可负，$|t|\le2\times10^{14}$；统计和严格小于 $t$ 的非空子段。

<details><summary>Hint 1</summary>子段 $[l,r]$ 对应前缀对 $P_r-P_{l-1}<t$。</details>
<details><summary>Hint 2</summary>改写为此前前缀 $P_{l-1}>P_r-t$。</details>

### 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 位。

### 核心伪代码与附件

```text
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 附件](../../参考实现/08-高级线段树与树状数组/CodeForces-1042D.cpp)

## 扩展与联系

## 高阶例题：Inversions

### 来源信息与题意

- VJudge：[AtCoder-agc023_e Inversions](https://vjudge.net/problem/AtCoder-agc023_e)
- 原题：[AtCoder Grand Contest 023 E](https://atcoder.jp/contests/agc023/tasks/agc023_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$。

<details><summary>Hint 1：先数合法排列</summary>

按数值从 $N$ 到 1 放置。放值 $x$ 时，可用位置数为

$$
c_x=\#\{i:A_i\ge x\}-(N-x).
$$

</details>

<details><summary>Hint 2：固定位置对，不要固定实际取值</summary>

对 $i<j$，若 $A_i\le A_j$，把一个合法排列中 $P_i,P_j$ 交换。哪些排列能两两配成“一顺一逆”？

</details>

<details><summary>Hint 3：把较大上界降到较小上界</summary>

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

</details>

<details><summary>Hint 4：上界下降后，排列数怎样变化</summary>

把一个上界从 $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，不能直接用逆元。

</details>

<details><summary>Hint 5：Fenwick 维护什么</summary>

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

</details>

### Observations

1. 枚举排列完全不可行；按值从大到小放置后，合法排列总数分解成独立乘积 $T=\prod_x c_x$。若某个 $c_x\le0$，不存在合法排列，答案立即为 0。
2. 线性期望虽能把答案写成 $T\sum_{i<j}\Pr(P_i>P_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)$。

固定 $i<j$。若 $A_i\le A_j$，在上述收紧后的排列集合里，$P_i,P_j\le A_i$，交换保持两个上界约束；排列中两值不同，交换是无不动点对合，每对恰有一个 $P_i>P_j$，贡献为 $TR/2$。若 $A_i>A_j$，完全相同的对合证明“不逆序”数为 $TR/2$，故逆序数为 $T-TR/2$。这覆盖每个位置对且每个排列逆序恰按其位置对计一次。

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

$$
Q_t=\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$。

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

```text
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](../../参考实现/08-高级线段树与树状数组/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 前先用一句中文写明“结构中当前有哪些对象”。若这句随扫描位置不成立，代码通常也会错。