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

## 扩展与联系

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

## 总结与自检

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

## 课后训练建议

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