# 数据结构基础
@@
## 目录
- 栈
- 概念
- 数组实现
- STL
- 队列
- 概念
- 数组实现、双栈实现
- 特殊队列
- STL
- 单调栈、单调队列
- 概念
- 实现
- 应用
@@
## 目录
- 并查集
- 概念
- 实现
- 复杂度
- 带权并查集
- ST表
- 概念
- 实现
- 树状数组
- 理解感受lowbit运算的魅力
- 实现
- 区间价区间和
- 二维树状数组
---
# 栈
@@
## 概念
栈是一种线性数据结构。
栈的修改与访问是按照 **后进先出** 的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。
   
@@
## 实现：数组模拟栈
```cpp
int st[N];
// 这里使用 st[0] (即 *st) 代表栈中元素数量，同时也是栈顶下标
// 压栈 ：
st[++*st] = var1;
// 取栈顶 ：
int u = st[*st];
// 弹栈 ：注意越界问题, *st == 0 时不能继续弹出
if (*st) --*st;
// 清空栈
*st = 0;
```
@@
## STL 中的栈
C++ 中的 STL 也提供了一个容器 ``` std::stack ```，使用前需要引入 ``` <stack> ``` 头文件。
STL 中的 ```stack``` 容器提供了一众成员函数以供调用，其中较为常用的有：
- 元素访问
- ```st.top()``` 返回栈顶
- 修改
- ```st.push()``` 插入传入的参数到栈顶
- ```st.pop()``` 弹出栈顶
- 容量
- ```st.empty()``` 返回是否为空
- ```st.size()``` 返回元素数量
@@
## STL 中的栈
此外，```std::stack``` 还提供了一些运算符。较为常用的是使用赋值运算符 $=$ 为 ```stack``` 赋值，示例：
```cpp
// 新建两个栈 st1 和 st2
std::stack<int> st1, st2;
// 为 st1 装入 1
st1.push(1);
// 将 st1 赋值给 st2
st2 = st1;
// 输出 st2 的栈顶元素
cout << st2.top() << endl;
// 输出: 1
```
---
# 队列
@@
## 概念
队列（queue）是一种具有「**先进入队列的元素一定先出队列**」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。
 
@@
## 实现：数组模拟队列
通常用一个数组模拟一个队列，用两个变量标记队列的首尾。
```cpp
int q[SIZE], ql = 1, qr;
```
队列操作对应的代码如下：
- 插入元素：```q[++qr] = x;```
- 删除元素：```ql++;```
- 访问队首：```q[ql]```
- 访问队尾：```q[qr]```
- 清空队列：```ql = 1; qr = 0;```
@@
## 实现：双栈模拟队列
这种方法使用两个栈 $F$, $S$ 模拟一个队列，其中 $F$ 是队尾的栈，$S$ 代表队首的栈，支持 push（在队尾插入），pop（在队首弹出）操作：
- ```push```：插入到栈 $F$ 中。
- ```pop```：如果 $S$ 非空，让 $S$ 弹栈；否则把 $F$ 的元素倒过来压到 $S$ 中（其实就是一个一个弹出插入，做完后是首尾颠倒的），然后再让 $S$ 弹栈。
@@
## STL 中的队列
C++ 在 STL 中提供了一个容器 `std::queue`，使用前需要先引入 `<queue>` 头文件。
STL 中的 ```queue``` 容器提供了一众成员函数以供调用。其中较为常用的有：
- 元素访问
- ```q.front()``` 返回队首元素
- ```q.back()``` 返回队尾元素
- 修改
- ```q.push()``` 在队尾插入元素
- ```q.pop()``` 弹出队首元素
- 容量
- ```q.empty()``` 队列是否为空
- ```q.size()``` 返回队列中元素的数量
@@
## STL 中的队列
此外，```queue``` 还提供了一些运算符。较为常用的是使用赋值运算符 `=` 为 ```queue``` 赋值，示例：
```cpp
std::queue<int> q1, q2;
// 向 q1 的队尾插入 1
q1.push(1);
// 将 q1 赋值给 q2
q2 = q1;
// 输出 q2 的队首元素
std::cout << q2.front() << std::endl;
// 输出: 1
```
@@
## 特殊队列：双端队列
双端队列是指一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合。具体地，双端队列支持的操作有 $4$ 个：
- 在队首插入一个元素
- 在队尾插入一个元素
- 在队首删除一个元素
- 在队尾删除一个元素
数组模拟双端队列的方式与普通队列相同。
@@
## STL 中的双端队列
C++ 在 STL 中也提供了一个容器 `std::deque`，使用前需要先引入 `<deque>` 头文件。
`deque` 提供了一众成员函数以供调用。其中较为常用的有：
- 元素访问
- `q.front()` 返回队首元素
- `q.back()` 返回队尾元素
- 修改
- `q.push_back()` 在队尾插入元素
- `q.pop_back()` 弹出队尾元素
- `q.push_front()` 在队首插入元素
- `q.pop_front()` 弹出队首元素
- `q.insert()` 在指定位置前插入元素（传入迭代器和元素）
- `q.erase()` 删除指定位置的元素（传入迭代器）
@@
## STL 中的双端队列
- 容量
- ```q.empty()``` 队列是否为空
- ```q.size()``` 返回队列中元素的数量
此外，```deque``` 还提供了一些运算符。其中较为常用的有：
- 使用赋值运算符 $=$ 为 ```deque``` 赋值，类似 ```queue```。
- 使用 `[]` 访问元素，类似 ```vector```。
@@
## 循环队列
使用数组模拟队列会导致一个问题：随着时间的推移，整个队列会向数组的尾部移动，一旦到达数组的最末端，即使数组的前端还有空闲位置，再进行入队操作也会导致溢出（这种数组里实际有空闲位置而发生了上溢的现象被称为「假溢出」）。
解决假溢出的办法是采用循环的方式来组织存放队列元素的数组，即将数组下标为 $0$ 的位置看做是最后一个位置的后继。（数组下标为 $x$ 的元素，它的后继为 $(x + 1) \ mod \ SIZE $）。这样就形成了循环队列。
---
# STL 扩展
@@
## 补充：二叉堆
从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。
大根堆性质：父亲的权值不小于儿子的权值。因此，树根存的是最大值。
同理我们可以定义小根堆：
小根堆性质：父亲的权值不大于儿子的权值。因此，树根存的是最小值。
@@
## STL：优先队列
优先队列 ```std::priority_queue``` 是一种堆，一般为二叉堆，使用前需要先引入 ```<queue>``` 头文件。
`priority_queue` 的成员函数：
以下所有函数均为常数复杂度
- ```top()``` 访问堆顶元素（此时优先队列不能为空）
- ```empty()``` 询问容器是否为空
- ```size()``` 查询容器中的元素数量
以下所有函数均为对数复杂度
- ```push(x)``` 插入元素，并对底层容器排序
- ```pop()``` 删除堆顶元素（此时优先队列不能为空）
@@
## 优先队列简单示例
```cpp
std::priority_queue<int> q1;
// 默认为大根堆
std::priority_queue<int, std::vector<int> > q2;
// C++11 后空格可省略
std::priority_queue<int, std::deque<int>, std::greater<int> > q3;
// q3 为小根堆
for (int i = 1; i <= 5; i++) q1.push(i);
// q1 中元素 : [1, 2, 3, 4, 5]
std::cout << q1.top() << std::endl;
// 输出结果 : 5
q1.pop();
// 堆中元素 : [1, 2, 3, 4]
std::cout << q1.size() << std::endl;
// 输出结果 ：4
for (int i = 1; i <= 5; i++) q3.push(i);
// q3 中元素 : [1, 2, 3, 4, 5]
std::cout << q3.top() << std::endl;
// 输出结果 : 1
```
@@
## 补充：重载运算符
重载运算符是通过对运算符的重新定义，使得其支持特定数据类型的运算操作。重载运算符是重载函数的特殊情况。
C++ 自带的运算符，最初只定义了一些基本类型的运算规则。当我们要在用户自定义的数据类型上使用这些运算符时，就需要定义运算符在这些特定类型上的运算方式。
受限于时间，我们这里只简单讲一下对结构体的比较运算符的重载
```cpp
struct student {
string name;
int score;
bool operator<(const student& a) const {
return score < a.score || (score == a.score && name > a.name);
// 上面省略了 this 指针，完整表达式如下：
// this->scorescore==a.score&&this->name>a.name);
}
};
priority_queue pq; //STL容器和sort中排序都是用的 <，因此重载 <
```
@@
## STL：set
```set``` 是关联容器，含有键值类型对象的已排序集，搜索、移除和插入拥有对数复杂度。```set``` 内部通常采用红黑树实现。平衡二叉树的特性使得 ```set``` 非常适合处理需要同时兼顾查找、插入与删除的情况。
和数学中的集合相似，```set``` 中不会出现值相同的元素。如果需要有相同元素的集合，需要使用 ```multiset```。```multiset``` 的使用方法与 ```set``` 的使用方法基本相同。
@@
## set 的插入与删除操作
- ```insert(x)``` 当容器中没有等价元素的时候，将元素 $x$ 插入到 ```set``` 中。
- ```erase(x)``` 删除值为 $x$ 的 所有 元素，返回删除元素的个数。
- ```erase(pos)``` 删除迭代器为 $pos$ 的元素，要求迭代器必须合法。
- ```erase(first,last)``` 删除迭代器在 $[first,last)$ 范围内的所有元素。
- ```clear()``` 清空 ```set```。
@@
## set 的迭代器
set 提供了以下几种迭代器：
- ```begin()/cbegin()``` 返回指向首元素的迭代器，其中 ```*begin = front```。
- ```end()/cend()``` 返回指向数组尾端占位符的迭代器，注意是没有元素的。
- ```rbegin()/crbegin()``` 返回指向逆向数组的首元素的逆向迭代器，可以理解为正向容器的末元素。
- ```rend()/crend()``` 返回指向逆向数组末元素后一位置的迭代器，对应容器首的前一个位置，没有元素。
@@
## set 的查找操作
- ```count(x)``` 返回 ```set``` 内键为 $x$ 的元素数量。
- ```find(x)``` 在 ```set``` 内存在键为 $x$ 的元素时会返回该元素的迭代器，否则返回 ```end()```。
- ```lower_bound(x)``` 返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回 ```end()```。
- ```upper_bound(x)``` 返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回 ```end()```。
- ```empty()``` 返回容器是否为空。
- ```size()``` 返回容器内元素个数。
@@
## set 示例：在贪心中的使用
在贪心算法中经常会需要出现类似 找出并删除最小的大于等于某个值的元素。这种操作能轻松地通过 ```set``` 来完成。
```cpp
// 现存可用的元素
set<int> available;
// 需要大于等于的值
int x;
// 查找最小的大于等于x的元素
set<int>::iterator it = available.lower_bound(x);
if (it == available.end()) {
// 不存在这样的元素，则进行相应操作……
} else {
// 找到了这样的元素，将其从现存可用元素中移除
available.erase(it);
// 进行相应操作……
}
```
@@
## STL：map
```map``` 是有序键值对容器，它的元素的键是唯一的。搜索、移除和插入操作拥有对数复杂度。```map``` 通常实现为 红黑树。
设想如下场景：现在需要存储一些键值对，例如存储学生姓名对应的分数：Tom 0，Bob 100，Alan 100。但是由于数组下标只能为非负整数，所以无法用姓名作为下标来存储，这个时候最简单的办法就是使用 STL 中的 ```map```。
```map``` 重载了 ```operator[]```，可以用任意定义了 ```operator < ``` 的类型作为下标（在 ```map``` 中叫做 $key$，也就是索引）：
```map<Key, T> yourMap;```
其中，Key 是键的类型，T 是值的类型，下面是使用 map 的实例：
```cpp
map<string, int> mp;
```
```map``` 中不会存在键相同的元素，```multimap``` 中允许多个元素拥有同一键。```multimap``` 的使用方法与 ```map``` 的使用方法基本相同。
@@
## map 的插入与删除操作
- 可以直接通过下标访问来进行查询或插入操作。例如 ```mp["Alan"]=100```。
- 通过向 ```map``` 中插入一个类型为 ```pair<Key, T>``` 的值可以达到插入元素的目的，例如 ```mp.insert(pair<string,int>("Alan",100));```。
- ```erase(key)``` 函数会删除键为 $key$ 的 所有 元素。返回值为删除元素的数量。
- ```erase(pos)```: 删除迭代器为 $pos$ 的元素，要求迭代器必须合法。
- ```erase(first,last)```: 删除迭代器在 $[first,last)$ 范围内的所有元素。
- ```clear()``` 函数会清空整个容器。
@@
## map 的查询操作
- ```count(x)```: 返回容器内键为 $x$ 的元素数量。复杂度为 $O(\log(size)+ans)$（关于容器大小对数复杂度，加上匹配个数）。
- ```find(x)```: 若容器内存在键为 $x$ 的元素，会返回该元素的迭代器；否则返回 ```end()```。
- ```lower_bound(x)```: 返回指向首个不小于给定键的元素的迭代器。
- ```upper_bound(x)```: 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 end()。
- ```empty()```: 返回容器是否为空。
- ```size()```: 返回容器内元素个数。
@@
## map 示例：存储复杂状态
在搜索中，我们有时需要存储一些较为复杂的状态（如坐标，无法离散化的数值，字符串等）以及与之有关的答案（如到达此状态的最小步数）。```map``` 可以用来实现此功能。其中的键是状态，而值是与之相关的答案。下面的展示了如何使用 ```map``` 存储以 ```string``` 表示的状态。
```cpp
// 存储状态与对应的答案
map<string, int> record;
// 新搜索到的状态与对应答案
string status;
int ans;
// 查找对应的状态是否出现过
map<string, int>::iterator it = record.find(status);
if (it == record.end()) {
// 尚未搜索过该状态，将其加入状态记录中
record[status] = ans;
// 进行相应操作……
} else {
// 已经搜索过该状态，进行相应操作……
}
```
---
# 单调栈与单调队列
@@
## 单调栈
单调栈即满足单调性的栈结构。
@@
## 单调栈的过程
将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。
例如，栈中自顶向下的元素为 $\{0,11,45,81\}$。
@@
## 单调栈的过程
插入元素 $14$ 时为了保证单调性需要依次弹出元素 $0$,$11$，操作后栈变为 $\{14,45,81\}$。
@@
## 单调栈的过程
用伪代码描述如下：
```cpp
insert x
while !sta.empty() && sta.top()<x
sta.pop()
sta.push(x)
```
@@
## 单调栈实例：[POJ3250 Bad Hair Day](http://poj.org/problem?id=3250)
有 $N$ 头牛从左到右排成一排，每头牛有一个高度 $h_i$，设左数第 $i$ 头牛与「它右边第一头高度 ≥$h_i$」的牛之间有 $c_i$ 头牛，试求 $\sum_{i=1}^{N} c_i$。
记录每头牛被弹出的位置，如果没有被弹出过则为最远端，稍微处理一下即可计算出题目所需结果。
@@
## 单调栈实例：离线RMQ问题
我们可以把所有询问按右端点排序，然后每次在序列上从左往右扫描到当前询问的右端点处，并把扫描到的元素插入到单调栈中。这样，每次回答询问时，单调栈中存储的值都是位置 $\le r$ 的、可能成为答案的决策点，并且这些元素满足单调性质。此时，单调栈上第一个位置 $\ge l$ 的元素就是当前询问的答案，这个过程可以用二分查找实现。使用单调栈解决 RMQ 问题的时间复杂度为 $O(q\log q + q\log n)$，空间复杂度为 $O(n)$。
- RMQ问题：RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。
@@
## 单调队列引入：[POJ2823 Sliding Window](http://poj.org/problem?id=2823)
本题大意是给出一个长度为 $n$ 的数组，编程输出每 $k$ 个连续的数中的最大值和最小值。
最暴力的想法很简单，对于每一段 $i \sim i+k-1$ 的序列，逐个比较来找出最大值（和最小值），时间复杂度约为 $O(n \times k)$。
容易发现，我们进行了许多重复的操作，这样显然会TLE
@@
## 单调队列概念
顾名思义，单调队列的重点分为「单调」和「队列」。
「单调」指的是元素的「规律」——递增（或递减）。
「队列」指的是元素只能从队头和队尾进行操作。
Ps. 单调队列中的 "队列" 与正常的队列有一定的区别，稍后会提到
@@
## 例题分析
有了上面「单调队列」的概念，很容易想到用单调队列进行优化。
要求的是每连续的 k 个数中的最大（最小）值，很明显，当一个数进入所要 "寻找" 最大值的范围中时，若这个数比其前面（先进队）的数要大，显然，前面的数会比这个数先出队且不再可能是最大值。
也就是说——当满足以上条件时，可将前面的数 "弹出"，再将该数真正 push 进队尾。
这就相当于维护了一个递减的队列，符合单调队列定义，减少了重复比较次数，不仅如此，由于维护出的队伍在查询范围内且递减，队头必定是该查询区域内的最大值，因此输出时只需输出队头即可。
显而易见的是，在这样的算法中，每个数只要进队与出队各一次，因此时间复杂度被降到了 $O(N)$。
而由于查询区间长度是固定的，超出查询空间的值再大也不能输出，因此还需要 site 数组记录第 i 个队中的数在原数组中的位置，以弹出越界的队头。
@@
## 过程
例如我们构造一个单调递增的队列会如下：
原序列为：$1 \ 3 \ -1 \ -3 \ 5 \ 3 \ 6 \ 7$ 且 $k=3$
因为我们始终要维护队列保证其 **递增** 的特点，所以会有如下的事情发生：
队列状态变化：$\{1\}$ $\{1 \ 3\}$ $\{-1\}$ $\{-3\}$ $\{-3 \ 5\}$ $\{-3 \ 3\}$ $\{3 \ 6\}$ $\{3 \ 6 \ 7\}$
Ps. 此处的 "队列" 跟普通队列的一大不同就在于可以从队尾进行操作，STL 中有类似的数据结构 deque。
---
# ST表
@@
## 定义
ST 表是用于解决 **可重复贡献问题** 的数据结构。
- 可重复贡献问题：是指对于运算 $\operatorname{opt}$，满足 $x\operatorname{opt} x=x$，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 $\max(x,x)=x$，gcd 有 $\operatorname{gcd}(x,x)=x$，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外，$\operatorname{opt}$ 还必须满足 **结合律** 才能使用 ST 表求解。
@@
## 引入例题
给定 $n$ 个数，有 $m$ 个询问，对于每个询问，你需要回答区间 $[l,r]$ 中的最大值。
考虑暴力做法。每次都对区间 $[l,r]$ 扫描一遍，求出最大值。显然，这个算法会超时。
@@
## ST 表概念
ST 表基于 **倍增** 思想，可以做到 $\Theta(n\log n)$ 预处理，$\Theta(1)$ 回答每个询问。但是不支持修改操作。
我们发现 $\max(x,x)=x$，也就是说，区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。
@@
## ST 表实现
令 $\operatorname{f}(i,j)$ 表示区间 $[i,i+2^j-1]$ 的最大值。
显然 $\operatorname{f}(i,0)=a_i$。
根据定义式，第二维就相当于倍增的时候「跳了 $2^j-1$ 步」，依据倍增的思路，写出状态转移方程：$\operatorname{f}(i,j)=\max(\operatorname{f}(i,j-1),\operatorname{f}(i+2^{j-1},j-1))$。
@@
## ST 表实现
以上就是预处理部分。而对于查询，可以简单实现如下：
对于每个询问 $[l,r]$，我们把它分成两部分：$[l,l+2^s-1]$ 与 $[r-2^s+1,r]$，其中 $s=\left\lfloor\log_2(r-l+1)\right\rfloor$。两部分的结果的最大值就是回答。
根据上面对于「可重复贡献问题」的论证，由于最大值是「可重复贡献问题」，重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 $[l,r]$，可以保证答案的正确性。
@@
## ST 表实现
```cpp
void pre() { // 准备工作，初始化
Logn[1] = 0;Logn[2] = 1;
for (int i = 3; i < maxn; i++) {
Logn[i] = Logn[i / 2] + 1;
}
}
int main() {
int n = read(), m = read();
for (int i = 1; i <= n; i++) f[i][0] = read();
pre();
for (int j = 1; j <= logn; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); // ST表具体实现
for (int i = 1; i <= m; i++) {
int x = read(), y = read();
int s = Logn[y - x + 1];
printf("%d\n", max(f[x][s], f[y - (1 << s) + 1][s]));
}
return 0;
}
```
@@
## ST 表应用
除 RMQ 以外，还有其它的「可重复贡献问题」。例如「区间按位和」、「区间按位或」、「区间 GCD」，ST 表都能高效地解决。
需要注意的是，对于「区间 GCD」，ST 表的查询复杂度并没有比线段树更优（令值域为 $w$，ST 表的查询复杂度为 $\Theta(\log w)$，而线段树为 $\Theta(\log n+\log w)$，且值域一般是大于 $n$ 的），但是 ST 表的预处理复杂度也没有比线段树更劣，而编程复杂度方面 ST 表比线段树简单很多。
如果分析一下，「可重复贡献问题」一般都带有某种类似 RMQ 的成分。例如「区间按位与」就是每一位取最小值，而「区间 GCD」则是每一个质因数的指数取最小值。
---
# 并查集
@@
## 并查集概念
并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
顾名思义，并查集支持两种操作：
- 合并（Union）：合并两个元素所属集合（合并对应的树）
- 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合
并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。
p.s. 并查集无法以较低复杂度实现集合的分离。
@@
## 并查集实现
初始化：初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。
```cpp
struct dsu {
vector<size_t> pa;
explicit dsu(size_t size) : pa(size) {
iota(pa.begin(), pa.end(), 0);
}
};
```
查询：我们需要沿着树向上移动，直至找到根节点。
@@
## 并查集实现：路径压缩
查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询。
```cpp
size_t dsu::find(size_t x) {
return pa[x] == x ? x : pa[x] = find(pa[x]);
}
```
@@
## 并查集实现：合并
要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。
```cpp
void dsu::unite(size_t x, size_t y) {
pa[find(x)] = find(y);
}
```
@@
## 并查集实现：启发式合并
合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。
按节点数合并的参考实现：
```cpp
struct dsu {
vector<size_t> pa, size;
explicit dsu(size_t size_) : pa(size_), size(size_, 1) {
iota(pa.begin(), pa.end(), 0);
}
void unite(size_t x, size_t y) {
x = find(x), y = find(y);
if (x == y) return;
if (size[x] < size[y]) swap(x, y);
pa[y] = x;
size[x] += size[y];
}
};
```
@@
## 并查集实现：删除
要删除一个叶子节点，我们可以将其父亲设为自己。为了保证要删除的元素都是叶子，我们可以预先为每个节点制作副本，并将其副本作为父亲。
```cpp
struct dsu {
vector<size_t> pa, size;
explicit dsu(size_t size_) : pa(size_ * 2), size(size_ * 2, 1) {
iota(pa.begin(), pa.begin() + size_, size_);
iota(pa.begin() + size_, pa.end(), size_);
}
void erase(size_t x) {
--size[find(x)];
pa[x] = x;
}
};
```
@@
## 并查集实现：移动
与删除类似，通过以副本作为父亲，保证要移动的元素都是叶子。
```cpp
void dsu::move(size_t x, size_t y) {
auto fx = find(x), fy = find(y);
if (fx == fy) return;
pa[x] = fy;
--size[fx], ++size[fy];
}
```
@@
## 启发式合并的时间复杂度
对于每个元素，当它当前所在的集合中，需要有其它大于该集合大小的集合，才会被遍历
如果元素在一个大小 $1$ 的集合中，会转移到大小 $2$ 的集合中
如果元素在一个大小 $2$ 的集合中，会转移到大小 $4$ 的集合中
如果元素在一个大小 $4$ 的集合中，会转移到大小 $8$ 的集合中
如果元素在一个大小 $8$ 的集合中，会转移到大小 $16$ 的集合中
因为一开始就进行按秩合并所以每次转移到两倍大小的集合中
所以每个元素转移 $\log n $ 次 那么总共 $O(n \log n)$
---
# 树状数组
@@
## 概念
树状数组是一种支持 **单点修改** 和 **区间查询** 的，代码量小的数据结构。
@@
## 「单点修改」和「区间查询」
已知一个数列 $a$，你需要进行下面两种操作：
- 给定 $x$, $y$，将 $a[x]$ 自增 $y$。
- 给定 $l$, $r$，求解 $a[l \ldots r]$ 的和。
其中第一种操作就是「单点修改」，第二种操作就是「区间查询」。
类似地，还有：「区间修改」、「单点查询」。它们分别的一个例子如下：
- 区间修改：给定 $l$, $r$, $x$，将 $a[l \ldots r]$ 中的每个数都分别自增 $x$；
- 单点查询：给定 $x$，求解 $a[x]$ 的值。
注意到，区间问题一般严格强于单点问题，因为对单点的操作相当于对一个长度为 $1$ 的区间操作。
@@
## 树状数组维护的信息性质
普通树状数组维护的信息及运算要满足 **结合律** 且 **可差分**，如加法（和）、乘法（积）、异或等。
- 结合律：$(x \circ y) \circ z = x \circ (y \circ z)$，其中 $\circ$ 是一个二元运算符。
- 可差分：具有逆运算的运算，即已知 $x \circ y$ 和 $x$ 可以求出 $y$。
需要注意的是：
- 模意义下的乘法若要可差分，需保证每个数都存在逆元（模数为质数时一定存在）；
- 例如 $\gcd$，$\max$ 这些信息不可差分，所以不能用普通树状数组处理，但是：
使用两个树状数组可以用于处理区间最值，见 [Efficient Range Minimum Queries using Binary Indexed Trees](https://ioi.te.lv/oi/files/volume9.pdf#page=41)。
@@
## 树状数组维护的信息性质
事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。
有时，在差分数组和辅助数组的帮助下，树状数组还可解决更强的 **区间加单点值** 和 **区间加区间和** 问题。
@@
## 树状数组原理
先来举个例子：我们想知道 $a[1 \ldots 7]$ 的前缀和，怎么做？
一种做法是：$a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7$，需要求 $7$ 个数的和。
但是如果已知三个数 $A$，$B$，$C$，$A = a[1 \ldots 4]$ 的和，$B = a[5 \ldots 6]$ 的总和，$C = a[7 \ldots 7]$ 的总和（其实就是 $a[7]$ 自己）。你会怎么算？你一定会回答：$A + B + C$，只需要求 $3$ 个数的和。
这就是树状数组能快速求解信息的原因：我们总能将一段前缀 $[1, n]$ 拆成 不多于 $\boldsymbol{\log n}$ 段区间，使得这 $\log n$ 段区间的信息是 已知的。
于是，我们只需合并这 $\log n$ 段区间的信息，就可以得到答案。相比于原来直接合并 n 个信息，效率有了很大的提高。
不难发现信息必须满足结合律，否则就不能像上面这样合并了。
@@
## 树状数组原理
下面这张图展示了树状数组的工作原理：
最下面的八个方块代表原始数据数组 $a$。上面参差不齐的方块（与最上面的八个方块是同一个数组）代表数组 $a$ 的上级——$c$ 数组。
$c$ 数组就是用来储存原始数组 $a$ 某段区间的和的，也就是说，这些区间的信息是已知的，我们的目标就是把查询前缀拆成这些小区间。
@@
例如，从图中可以看出：
- $c_2$ 管辖的是 $a[1 \ldots 2]$；
- $c_4$ 管辖的是 $a[1 \ldots 4]$；
- $c_6$ 管辖的是 $a[5 \ldots 6]$；
- $c_8$ 管辖的是 $a[1 \ldots 8]$；
剩下的 $c[x]$ 管辖的都是 $a[x]$ 自己（可以看做 $a[x \ldots x]$ 的长度为 $1$ 的小区间）。
不难发现，$c[x]$ 管辖的一定是一段右边界是 $x$ 的区间总信息。我们先不关心左边界，先来感受一下树状数组是如何查询的。
@@
举例：计算 $a[1 \ldots 7]$ 的和。
过程：从 $c_{7}$ 开始往前跳，发现 $c_{7}$ 只管辖 $a_{7}$ 这个元素；然后找 $c_{6}$，发现 $c_{6}$ 管辖的是 $a[5 \ldots 6]$，然后跳到 $c_{4}$，发现 $c_{4}$ 管辖的是 $a[1 \ldots 4]$ 这些元素，然后再试图跳到 $c_0$，但事实上 $c_0$ 不存在，不跳了。
我们刚刚找到的 $c$ 是 $c_7$, $c_6$, $c_4$，事实上这就是 $a[1 \ldots 7]$ 拆分出的三个小区间，合并得到答案是 $c_7$ + $c_6$ + $c_4$。
@@
举例：计算 $a[4 \ldots 7]$ 的和。
我们还是从 $c_7$ 开始跳，跳到 $c_6$ 再跳到 $c_4$。此时我们发现它管理了 $a[1 \ldots 4]$ 的和，但是我们不想要 $a[1 \ldots 3]$ 这一部分，怎么办呢？很简单，减去 $a[1 \ldots 3]$ 的和就行了。
那不妨考虑最开始，就将查询 $a[4 \ldots 7]$ 的和转化为查询 $a[1 \ldots 7]$ 的和，以及查询 $a[1 \ldots 3]$ 的和，最终将两个结果作差。
@@
## 树状数组：管辖区间
那么问题来了，$c[x](x \ge 1)$ 管辖的区间到底往左延伸多少？也就是说，区间长度是多少？
树状数组中，规定 $c[x]$ 管辖的区间长度为 $2^{k}$，其中：
- 设二进制最低位为第 $0$ 位，则 $k$ 恰好为 $x$ 二进制表示中，最低位的 $1$ 所在的二进制位数；
- $2^k$（$c[x]$ 的管辖区间长度）恰好为 $x$ 二进制表示中，最低位的 $1$ 以及后面所有 $0$ 组成的数。
@@
## 树状数组：管辖区间
举个例子，$c_{88}$ 管辖的是哪个区间？
因为 $88_{(10)}=01011000_{(2)}$，其二进制最低位的 $1$ 以及后面的 $0$ 组成的二进制是 $1000$，即 $8$，所以 $c_{88}$ 管辖 $8$ 个 $a$ 数组中的元素。
因此，$c_{88}$ 代表 $a[81 \ldots 88]$ 的区间信息。
我们记 $x$ 二进制最低位 $1$ 以及后面的 $0$ 组成的数为 $\operatorname{lowbit}(x)$，那么 $c[x]$ 管辖的区间就是 $[x-\operatorname{lowbit}(x)+1, x]$。
p.s. 这里注意：$\boldsymbol{\operatorname{lowbit}}$ 指的不是最低位 $1$ 所在的位数 $\boldsymbol{k}$，而是这个 $1$ 和后面所有 $0$ 组成的 $\boldsymbol{2^k}$。
@@
## lowbit
怎么计算 $\mathrm{lowbit}$？根据位运算知识可得 `$ \operatorname{lowbit}(x) = x \& -x$`。
原理如下：
将 $x$ 的二进制所有位全部取反，再加 $1$，就可以得到 $-x$ 的二进制编码。例如，$6$ 的二进制编码是 $110$，全部取反后得到 $001$，加 $1$ 得到 $010$。
设原先 $x$ 的二进制编码是 $(...)10...00$，全部取反后得到 $[...]01...11$，加 $1$ 后得到 $[...]10...00$，也就是 $-x$ 的二进制编码了。这里 $x$ 二进制表示中第一个 $1$ 是 $x$ 最低位的 $1$。
$(...)$ 和 $[...]$ 中省略号的每一位分别相反，所以 `$x \ \& -x = (...)10...00 \ \& \ [...]10...00 = 10...00$`，得到的结果就是 $\mathrm{lowbit}$。
实现：`int lowbit(int x) {return x & -x;}`
@@
## 树状数组：区间查询
接下来我们来看树状数组具体的操作实现，先来看区间查询。
回顾查询 $a[4 \ldots 7]$ 的过程，我们是将它转化为两个子过程：查询 $a[1 \ldots 7]$ 和查询 $a[1 \ldots 3]$ 的和，最终作差。
其实任何一个区间查询都可以这么做：查询 $a[l \ldots r]$ 的和，就是 $a[1 \ldots r]$ 的和减去 $a[1 \ldots l - 1]$ 的和，从而把区间问题转化为前缀问题，更方便处理。
事实上，将有关 $l \ldots r$ 的区间询问转化为 $1 \ldots r$ 和 $1 \ldots l - 1$ 的前缀询问再差分，在竞赛中是一个非常常用的技巧。
@@
## 树状数组：前缀查询
那前缀查询怎么做呢？回顾下查询 $a[1 \ldots 7]$ 的过程：
- 从 $c_{7}$ 往前跳，发现 $c_{7}$ 只管辖 $a_{7}$ 这个元素；然后找 $c_{6}$，发现 $c_{6}$ 管辖的是 $a[5 \ldots 6]$，然后跳到 $c_{4}$，发现 $c_{4}$ 管辖的是 $a[1 \ldots 4]$ 这些元素，然后再试图跳到 $c_0$，但事实上 $c_0$ 不存在，不跳了。
- 我们刚刚找到的 $c$ 是 $c_7$, $c_6$, $c_4$，事实上这就是 $a[1 \ldots 7]$ 拆分出的三个小区间，合并一下，答案是 $c_7 + c_6 + c_4$。
观察上面的过程，每次往前跳，一定是跳到现区间的左端点的左一位，作为新区间的右端点，这样才能将前缀不重不漏地拆分。比如现在 $c_6$ 管的是 $a[5 \ldots 6]$，下一次就跳到 $5 - 1 = 4$，即访问 $c_4$。
@@
## 树状数组：前缀查询
我们可以写出查询 $a[1 \ldots x]$ 的过程：
- 从 $c[x]$ 开始往前跳，有 $c[x]$ 管辖 $a[x-\operatorname{lowbit}(x)+1 \ldots x]$；
令 $x \gets x - \operatorname{lowbit}(x)$，如果 $x = 0$ 说明已经跳到尽头了，终止循环；否则回到第一步。
- 将跳到的 $c$ 合并。
- 实现时，我们不一定要先把 $c$ 都跳出来然后一起合并，可以边跳边合并。
比如我们要维护的信息是和，直接令初始 $\mathrm{ans} = 0$，然后每跳到一个 $c[x]$ 就 $\mathrm{ans} \gets \mathrm{ans} + c[x]$，最终 $\mathrm{ans}$ 就是所有合并的结果。
@@
## 树状数组：前缀查询实现
```cpp
int getsum(int x) { // a[1]..a[x]的和
int ans = 0;
while (x > 0) {
ans = ans + c[x];
x = x - lowbit(x);
}
return ans;
}
```
@@
## 树状数组与其树形态的性质
在讲解单点修改之前，先讲解树状数组的一些基本性质，以及其树形态来源，这有助于更好理解树状数组的单点修改。
我们约定：
- $\operatorname{l}(x) = x - \operatorname{lowbit}(x) + 1$。即，$l(x)$ 是 $c[x]$ 管辖范围的左端点。
- 对于任意正整数 $x$，总能将 $x$ 表示成 $s \times 2^{k + 1} + 2^k$ 的形式，其中 $\operatorname{lowbit}(x) = 2^k$。
- 下面「$c[x]$ 和 $c[y]$ 不交」指 $c[x]$ 的管辖范围和 $c[y]$ 的管辖范围不相交，即 [$l(x)$, $x$] 和 [$l(y)$, $y$] 不相交。「$c[x]$ 包含于 $c[y]$」等表述同理。
@@
### 性质 $\boldsymbol{1}$：对于 $\boldsymbol{x \le y}$，要么有 $\boldsymbol{c[x]}$ 和 $\boldsymbol{c[y]}$ 不交，要么有 $\boldsymbol{c[x]}$ 包含于 $\boldsymbol{c[y]}$。
证明：假设 $c[x]$ 和 $c[y]$ 相交，即 $[l(x), x]$ 和 $[l(y), y]$ 相交，则一定有 $l(y) \le x \le y$。
将 $y$ 表示为 $s \times 2^{k +1} + 2^k$，则 $l(y) = s \times 2^{k + 1} + 1$。所以，$x $可以表示为 $s \times 2^{k +1} + b$，其中 $1 \le b \le 2^k$。
不难发现 $\operatorname{lowbit}(x) = \operatorname{lowbit}(b)$。又因为 $b - \operatorname{lowbit}(b) \ge 0$，
所以 $l(x) = x - \operatorname{lowbit}(x) + 1 = s \times 2^{k +1} + b - \operatorname{lowbit}(b) +1 \ge s \times 2^{k +1} + 1 = l(y)$，即 $l(y) \le l(x) \le x \le y$。
所以，如果 $c[x]$ 和 $c[y]$ 相交，那么 $c[x]$ 的管辖范围一定完全包含于 $c[y]$。
@@
### 性质 $\boldsymbol{2}$：在 $\boldsymbol{c[x]}$ 真包含于 $\boldsymbol{c[x + \operatorname{lowbit}(x)]}$。
证明：设 $y = x + \operatorname{lowbit}(x)$，$x = s \times 2^{k + 1} + 2^k$，则 $y = (s + 1) \times 2^{k +1}$，$l(x) = s \times 2^{k + 1} + 1$。
不难发现 $\operatorname{lowbit}(y) \ge 2^{k + 1}$，所以 $l(y) = (s + 1) \times 2^{k + 1} - \operatorname{lowbit}(y) + 1 \le s \times 2^{k +1} + 1= l(x)，即 l(y) \le l(x) \le x < y$。
所以，$c[x]$ 真包含于 $c[x + \operatorname{lowbit}(x)]$。
@@
### 性质 $\boldsymbol{3}$：对于任意 $\boldsymbol{x < y < x + \operatorname{lowbit}(x)}$，有 $\boldsymbol{c[x]}$ 和 $\boldsymbol{c[y]}$ 不交。
证明：设 $x = s \times 2^{k + 1} + 2^k$，则 $y = x + b = s \times 2^{k + 1} + 2^k + b$，其中 $1 \le b < 2^k$。
不难发现 $\operatorname{lowbit}(y) = \operatorname{lowbit}(b)$。又因为 $b - \operatorname{lowbit}(b) \ge 0$，
因此 $l(y) = y - \operatorname{lowbit}(y) + 1 = x + b - \operatorname{lowbit}(b) + 1 > x$，即 $l(x) \le x < l(y) \le y$。
所以，$c[x]$ 和 $c[y]$ 不交。
@@
有了这三条性质的铺垫，我们接下来看树状数组的树形态（请忽略 $a$ 向 $c$ 的连边）。
事实上，树状数组的树形态是 $x$ 向 $x + \operatorname{lowbit}(x)$ 连边得到的图，其中 $x$ + $\operatorname{lowbit}(x)$ 是 $x$ 的父亲。
@@
注意，在考虑树状数组的树形态时，我们不考虑树状数组大小的影响，即我们认为这是一棵无限大的树，方便分析。实际实现时，我们只需用到 $x \le n$ 的 $c[x]$，其中 $n$ 是原数组长度。
@@
这棵树天然满足了很多美好性质，下面列举若干（设 $fa[u]$ 表示 $u$ 的直系父亲）：
- $u < fa[u]$。
- $u$ 大于任何一个 $u$ 的后代，小于任何一个 $u$ 的祖先。
- 点 $u$ 的 $\operatorname{lowbit}$ 严格小于 $fa[u]$ 的 $\operatorname{lowbit}$。
证明：设 $y = x + \operatorname{lowbit}(x)$，$x = s \times 2^{k + 1} + 2^k$，则 $y = (s + 1) \times 2^{k +1}$，不难发现 $\operatorname{lowbit}(y) \ge 2^{k + 1} > \operatorname{lowbit}(x)$，证毕。
@@
- 点 $x$ 的高度是 $\log_2\operatorname{lowbit}(x)$，即 $x$ 二进制最低位 $1$ 的位数。
- $c[u]$ 真包含于 $c[fa[u]]$（性质 2）。
- $c[u]$ 真包含于 $c[v]$，其中 $v$ 是 $u$ 的任一祖先（在上一条性质上归纳）。
- $c[u]$ 真包含 $c[v]$，其中 $v$ 是 $u$ 的任一后代（上面那条性质 $u$，$v$ 颠倒）。
- 对于任意 $v' > u$，若 $v'$ 不是 $u$ 的祖先，则 $c[u]$ 和 $c[v']$ 不交。
证明：$u$ 和 $u$ 的祖先中，一定存在一个点 $v$ 使得 $v < v' < fa[v]$，根据性质 $3$ 得 $c[v']$ 不相交于 $c[v]$，而 $c[v]$ 包含 $c[u]$，因此 $c[v']$ 不交于 $c[u]$。
@@
- 对于任意 $v < u$，如果 $v$ 不在 $u$ 的子树上，则 $c[u]$ 和 $c[v]$ 不交（上面那条性质 $u$，$v'$ 颠倒）。
- 对于任意 $v$ > $u$，当且仅当 $v$ 是 $u$ 的祖先，$c[u]$ 真包含于 $c[v]$（上面几条性质的总结）。这就是树状数组单点修改的核心原理。
- 设 $u = s \times 2^{k + 1} + 2^k$，则其儿子数量为 $k = \log_2\operatorname{lowbit}(u)$，编号分别为 $u - 2^t(0 \le t < k)$。
- 举例：假设 $k = 3$，$u$ 的二进制编号为 $...1000$，则 $u$ 有三个儿子，二进制编号分别为 $...0111$、$...0110$、$...0100$。
@@
证明：在一个数 $x$ 的基础上减去 $2^t$，$x$ 二进制第 $t$ 位会反转，而更低的位保持不变。
- 考虑 $u$ 的儿子 $v$，有 $v + \operatorname{lowbit}(v) = u$，即 $v = u - 2^t$ 且 $\operatorname{lowbit}(v) = 2^t$。设 $u = s \times 2^{k + 1} + 2^k$。
- 考虑 $\boldsymbol{0 \le t < k}$，$u$ 的第 $t$ 位及后方均为 $0$，所以 $v = u - 2^t$ 的第 $t$ 位变为 $1$，后面仍为 $0$，满足 $\operatorname{lowbit}(v) = 2^t$。
- 考虑 $\boldsymbol{t = k}$，则 $v = u - 2^k$，$v$ 的第 $k$ 位变为 $0$，不满足 $\operatorname{lowbit}(v) = 2^t$。
- 考虑 $\boldsymbol{t > k}$，则 $v = u - 2^t$，$v$ 的第 $k$ 位是 $1$，所以 $\operatorname{lowbit}(v) = 2^k$，不满足 $\operatorname{lowbit}(v) = 2^t$。
@@
- $u$ 的所有儿子对应 $c$ 的管辖区间恰好拼接成 $[l(u), u - 1]$。
- 举例：假设 $k = 3$，$u$ 的二进制编号为 $...1000$，则 $u$ 有三个儿子，二进制编号分别为 $...0111$、$...0110$、$...0100$。
- $c[...0100]$ 表示 $a[...0001 ~ ...0100]$。
- $c[...0110]$ 表示 $a[...0101 ~ ...0110]$。
- $c[...0111]$ 表示 $a[...0111 ~ ...0111]$。
- 不难发现上面是三个管辖区间的并集恰好是 $a[...0001 ~ ...0111]$，即 $[l(u), u - 1]$。
@@
证明：$u$ 的儿子总能表示成 $u - 2^t(0 \le t < k)$，不难发现，$t$ 越小，$u - 2^t$ 越大，代表的区间越靠右。我们设 $f(t) = u - 2^t$，则 $f(k - 1), f(k - 2), \ldots, f(0)$ 分别构成 $u$ 从左到右的儿子。
不难发现 $\operatorname{lowbit}(f(t)) = 2^t$，所以 $l(f(t)) = u - 2^t - 2^t + 1 = u - 2^{t + 1} + 1$。
考虑相邻的两个儿子 $f(t + 1)$ 和 $f(t)$。前者管辖区间的右端点是 $f(t + 1) = u - 2^{t + 1}$，后者管辖区间的左端点是 $l(f(t)) = u - 2^{t + 1} + 1$，恰好相接。
考虑最左面的儿子 $f(k - 1)$，其管辖左边界 $l(f(k - 1)) = u - 2^k + 1$ 恰为 $l(u)$。
考虑最右面的儿子 $f(0)$，其管辖右边界就是 $u - 1$。
因此，这些儿子的管辖区间可以恰好拼成 $[l(u), u - 1]$。
@@
## 单点修改
现在来考虑如何单点修改 $a[x]$。
我们的目标是快速正确地维护 $c$ 数组。为保证效率，我们只需遍历并修改管辖了 $a[x]$ 的所有 $c[y]$，因为其他的 $c$ 显然没有发生变化。
管辖 $a[x]$ 的 $c[y]$ 一定包含 $c[x]$（根据性质 $1$），所以 $y$ 在树状数组树形态上是 $x$ 的祖先。因此我们从 $x$ 开始不断跳父亲，直到跳得超过了原数组长度为止。
设 $n$ 表示 $a$ 的大小，不难写出单点修改 $a[x]$ 的过程：
- 初始令 $x' = x$。
- 修改 $c[x']$。
- 令 $x' \gets x' + \operatorname{lowbit}(x')$，如果 $x' > n$ 说明已经跳到尽头了，终止循环；否则回到第二步。
@@
## 单点修改
区间信息和单点修改的种类，共同决定 $c[x']$ 的修改方式。下面给几个例子：
- 若 $c[x']$ 维护区间和，修改种类是将 $a[x]$ 加上 $p$，则修改方式则是将所有 $c[x']$ 也加上 $p$。
- 若 $c[x']$ 维护区间积，修改种类是将 $a[x]$ 乘上 $p$，则修改方式则是将所有 $c[x']$ 也乘上 $p$。
然而，单点修改的自由性使得修改的种类和维护的信息不一定是同种运算，比如，若 $c[x']$ 维护区间和，修改种类是将 $a[x]$ 赋值为 $p$，可以考虑转化为将 $a[x]$ 加上 $p - a[x]$。如果是将 $a[x]$ 乘上 $p$，就考虑转化为 $a[x]$ 加上 $a[x] \times p - a[x]$。
@@
## 单点修改
下面以维护区间和，单点加为例给出实现。
```cpp
void add(int x, int k) {
while (x <= n) { // 不能越界
c[x] = c[x] + k;
x = x + lowbit(x);
}
}
```
@@
## 建树
也就是根据最开始给出的序列，将树状数组建出来（$c$ 全部预处理好）。
一般可以直接转化为 $n$ 次单点修改，时间复杂度 $\Theta(n \log n)$。
比如给定序列 $a = (5, 1, 4)$ 要求建树，直接看作对 $a[1]$ 单点加 $5$，对 $a[2]$ 单点加 $1$，对 $a[3]$ 单点加 $4$ 即可。
@@
## 区间加区间和
前置知识：**前缀和** & **差分**。
该问题可以使用两个树状数组维护差分数组解决。
考虑序列 $a$ 的差分数组 $d$，其中 $d[i] = a[i] - a[i - 1]$。由于差分数组的前缀和就是原数组，所以 $a_i=\sum_{j=1}^i d_j$。
一样地，我们考虑将查询区间和通过差分转化为查询前缀和。那么考虑查询 $a[1 \ldots r]$ 的和，即
$\sum_{i=1}^{r} a_i$，进行推导：
`$$
\begin{aligned} &\sum_{i=1}^{r}a_i = &\sum_{i=1}^r\sum_{j=1}^i d_j \end{aligned}
$$`
@@
## 区间加区间和
观察这个式子，不难发现每个 $d_j$ 总共被加了 $r - j + 1$ 次。接着推导：
`$$
\begin{aligned}\sum_{i=1}^r\sum_{j=1}^i d_j=\sum_{i=1}^r d_i\times(r-i+1)\\
=\sum_{i=1}^r d_i\times (r+1)-\sum_{i=1}^r d_i\times i \end{aligned}
$$`
$\sum_{i=1}^r d_i$ 并不能推出
$\sum_{i=1}^r d_i \times i$ 的值，所以要用两个树状数组分别维护 $d_i$ 和 $d_i \times i$ 的和信息。
@@
## 区间加区间和
那么怎么做区间加呢？考虑给原数组 $a[l \ldots r]$ 区间加 $x$ 给 $d$ 带来的影响。
因为差分是 $d[i] = a[i] - a[i - 1]$，
$a[l]$ 多了 $v$ 而 $a[l - 1]$ 不变，所以 $d[l]$ 的值多了 $v$。
$a[r + 1]$ 不变而 $a[r]$ 多了 $v$，所以 $d[r + 1]$ 的值少了 $v$。
对于不等于 $l$ 且不等于 $r+1$ 的任意 $i$，$a[i]$ 和 $a[i - 1]$ 要么都没发生变化，要么都加了 $v$，$a[i] + v - (a[i - 1] + v)$ 还是 $a[i] - a[i - 1]$，所以其它的 $d[i]$ 均不变。
那就不难想到维护方式了：对于维护 $d_i$ 的树状数组，对 $l$ 单点加 $v$，$r + 1$ 单点加 $-v$；对于维护 $d_i \times i$ 的树状数组，对 $l$ 单点加 $v \times l$，$r + 1$ 单点加 $-v \times (r + 1)$。
而更弱的问题，「区间加求单点值」，只需用树状数组维护一个差分数组 $d_i$。询问 $a[x]$ 的单点值，直接求 $d[1 \ldots x]$ 的和即可。
@@
这里直接给出「区间加区间和」的代码：
```cpp
void add(int k, int v) {
int v1 = k * v;
while (k <= n) {
t1[k] += v, t2[k] += v1;//注意不能写成 t2[k]+=k*v，因为k的值已经不是原数组的下标了
k += lowbit(k);
}
}
int getsum(int *t, int k) {
int ret = 0;
while (k) {
ret += t[k];
k -= lowbit(k);
}
return ret;
}
void add1(int l, int r, int v) {
add(l, v), add(r + 1, -v); //将区间加差分为两个前缀加
}
long long getsum1(int l, int r) {
return (r+1)*getsum(t1,r) - l*getsum(t1,l-1) - (getsum(t2,r) - getsum(t2,l-1));
}
```
@@
## 二维树状数组：单点修改，子矩阵查询
二维树状数组，也被称作树状数组套树状数组，用来维护二维数组上的单点修改和前缀信息问题。
与一维树状数组类似，我们用 $c(x, y)$ 表示 $a(x - \operatorname{lowbit}(x) + 1, y - \operatorname{lowbit}(y) + 1) \ldots a(x, y)$ 的矩阵总信息，即一个以 $a(x, y)$ 为右下角，高 $\operatorname{lowbit}(x)$，宽 $\operatorname{lowbit}(y)$ 的矩阵的总信息。
对于单点修改，设：
`$f(x, i) = \begin{cases}x &i = 0\\f(x, i - 1) + \operatorname{lowbit}(f(x, i - 1)) & i > 0\\\end{cases}$`
即 $f(x, i)$ 为 $x$ 在树状数组树形态上的第 $i$ 级祖先（第 $0$ 级祖先是自己）。
则只有 $c(f(x, i), f(y, j))$ 中的元素管辖 $a(x, y)$，修改 $a(x, y)$ 时只需修改所有 $c(f(x, i), f(y, j))$，其中 $f(x, i) \le n$，$f(y, j) \le m$。
@@
## 二维树状数组：单点修改，子矩阵查询
对于查询，我们设：
`$g(x, i) = \begin{cases}x &i = 0\\g(x, i - 1) - \operatorname{lowbit}(g(x, i - 1)) & i, g(x, i - 1) > 0\\0&\text{otherwise.}\end{cases}$`
则合并所有 $c(g(x, i), g(y, j))$，其中 $g(x, i), g(y, j) > 0$。
下面给出单点加、查询子矩阵和的代码。
```cpp
void add(int x, int y, int v) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
// 注意这里必须得建循环变量，不能像一维数组一样直接 while (x <= n) 了
c[i][j] += v;
}
}
}
```
@@
## 子矩阵加
和一维树状数组的「区间加区间和」问题类似，考虑维护差分数组。
二维数组上的差分数组是这样的：$d(i, j) = a(i, j) - a(i - 1, j) - a(i, j - 1) + a(i - 1, j - 1)$
这样以来，对左上角 $(x_1, y_1)$，右下角 $(x_2, y_2)$ 的子矩阵区间加 $v$，相当于在差分数组上，对 $d(x_1, y_1)$ 和 $d(x_2 + 1, y_2 + 1)$ 分别单点加 $v$，对 $d(x_2 + 1, y_1)$ 和 $d(x_1, y_2 + 1)$ 分别单点加 $-v$。
原因：把这四个 $d$ 分别用定义式表示出来，分析一下每项的变化即可。
@@
## 子矩阵加
举个例子，初始差分数组为 0，给 $a(2, 2) \ldots a(3, 4)$ 子矩阵加 v 后差分数组会变为：
`$\begin{pmatrix}0&0&0&0&0\\0&v&0&0&-v\\0&0&0&0&0\\0&-v&0&0&v\end{pmatrix}$`
（其中 $a(2, 2) \ldots a(3, 4)$ 这个子矩阵恰好是上面位于中心的 $2 \times 3$ 大小的矩阵。）
因此，子矩阵加的做法是：转化为差分数组上的四个单点加操作。
@@
## 求子矩阵和
现在考虑查询子矩阵和：
对于点 (x, y)，它的二维前缀和可以表示为：
$\sum_{i = 1}^x\sum_{j = 1}^y\sum_{h = 1}^i\sum_{k = 1}^j d(h, k)$
原因就是差分的前缀和的前缀和就是原本的前缀和。
和一维树状数组的「区间加区间和」问题类似，统计 $d(h, k)$ 的出现次数，为 $(x - h + 1) \times (y - k + 1)$。
@@
## 求子矩阵和
接着推导：
`$\begin{aligned}
&\sum_{i = 1}^x\sum_{j = 1}^y\sum_{h = 1}^i\sum_{k = 1}^j d(h, k)
\\=&\sum_{i = 1}^x\sum_{j = 1}^y d(i, j) \times (x - i + 1) \times (y - j + 1)
\\=&\sum_{i = 1}^x\sum_{j = 1}^y d(i, j) \times (xy + x + y + 1) - d(i, j) \times i \times (y + 1) - d(i, j) \times j \times (x + 1) + d(i, j) \times i \times j
\end{aligned}$`
所以我们需维护四个树状数组，分别维护 $d(i, j)$，$d(i, j) \times i$，$d(i, j) \times j$，$d(i, j) \times i \times j$ 的和信息。
当然了，和一维同理，如果只需要子矩阵加求单点值，维护一个差分数组然后询问前缀和就足够了。
@@
```cpp
void add(ll x, ll y, ll z) {
for (int X = x; X <= n; X += lowbit(X))
for (int Y = y; Y <= m; Y += lowbit(Y)) {
t1[X][Y] += z;
t2[X][Y] += z * x; // 注意是 z * x 而不是 z * X，后面同理
t3[X][Y] += z * y;
t4[X][Y] += z * x * y;
}
}
void range_add(ll xa, ll ya, ll xb, ll yb, ll z) { //(xa, ya) 到 (xb, yb) 子矩阵
add(xa, ya, z);
add(xa, yb + 1, -z);
add(xb + 1, ya, -z);
add(xb + 1, yb + 1, z);
}
ll ask(ll x, ll y) {
ll res = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
res += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] -
(x + 1) * t3[i][j] + t4[i][j];
return res;
}
ll range_ask(ll xa, ll ya, ll xb, ll yb) {
return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
}
```
@@
## 权值树状数组及应用
我们可以在原序列的权值数组上构建树状数组，这就是权值树状数组。
### 权值数组
一个序列 $a$ 的权值数组 $b$，满足 $b[x]$ 的值为 $x$ 在 $a$ 中的出现次数。
例如：$a = (1, 3, 4, 3, 4)$ 的权值数组为 $b = (1, 0, 2, 2)$。
很明显，$b$ 的大小和 $a$ 的值域有关。
若原数列值域过大，且重要的不是具体值而是值与值之间的相对大小关系，常 离散化 原数组后再建立权值数组。
另外，权值数组是原数组无序性的一种表示：它重点描述数组的元素内容，忽略了数组的顺序，若两数组只是顺序不同，所含内容一致，则它们的权值数组相同。
运用权值树状数组，我们可以解决一些经典问题。
@@
### 单点修改，查询全局第 $k$ 小
在此处只讨论第 $k$ 小，第 $k$ 大问题可以通过简单计算转化为第 $k$ 小问题。
该问题可离散化，如果原序列 $a$ 值域过大，离散化后再建立权值数组 $b$。注意，还要把单点修改中的涉及到的值也一起离散化，不能只离散化原数组 $a$ 中的元素。
对于单点修改，只需将对原数列的单点修改转化为对权值数组的单点修改即可。具体来说，原数组 $a[x]$ 从 $y$ 修改为 $z$，转化为对权值数组 $b$ 的单点修改就是 $b[y]$ 单点减 $1$，$b[z]$ 单点加 $1$。
对于查询第 $k$ 小，考虑二分 $x$，查询权值数组中 $[1, x]$ 的前缀和，找到 $x_0$ 使得 $[1, x_0]$ 的前缀和 $< k$ 而 $[1, x_0 + 1]$ 的前缀和 $\ge k$，则第 $k$ 大的数是 $x_0 + 1$（注：这里认为 $[1, 0]$ 的前缀和是 $0$）。
这样做时间复杂度是 $\Theta(\log^2n)$ 的。
@@
考虑用倍增替代二分。
设 $x = 0，\mathrm{sum} = 0$，枚举 $i$ 从 $\log_2n$ 降为 $0$：
查询权值数组中 $[x + 1 \ldots x + 2^i]$ 的区间和 $t$。
如果 $\mathrm{sum} + t < k$，扩展成功，$x \gets x + 2^i$，$\mathrm{sum} \gets \mathrm{sum} + t$；否则扩展失败，不操作。
这样得到的 $x$ 是满足 $[1 \ldots x]$ 前缀和 $< k$ 的最大值，所以最终 $x + 1$ 就是答案。
看起来这种方法时间效率没有任何改善，但事实上，查询 $[x + 1 \ldots x + 2^i]$ 的区间和只需访问 $c[x + 2^i]$ 的值即可。
原因很简单，考虑 $\operatorname{lowbit}(x + 2^i)$，它一定是 $2^i$，因为 $x$ 之前只累加过 $2^j$ 满足 $j > i$。因此 $c[x + 2^i]$ 表示的区间就是 $[x + 1 \ldots x + 2^i]$。
如此以来，时间复杂度降低为 $\Theta(\log n)$。
@@
代码实现：
```cpp
// 权值树状数组查询第 k 小
int kth(int k) {
int sum = 0, x = 0;
for (int i = log2(n); ~i; --i) {
x += 1 << i; // 尝试扩展
if (x >= n || sum + t[x] >= k) // 如果扩展失败
x -= 1 << i;
else
sum += t[x];
}
return x + 1;
}
```
@@
### 全局逆序对（全局二维偏序）
全局逆序对也可以用权值树状数组巧妙解决。问题是这样的：给定长度为 $n$ 的序列 $a$，求 $a$ 中满足 $i < j$ 且 $a[i] > a[j]$ 的数对 $(i, j)$ 的数量。
该问题可离散化，如果原序列 $a$ 值域过大，离散化后再建立权值数组 $b$。
我们考虑从 $n$ 到 $1$ 倒序枚举 $i$，作为逆序对中第一个元素的索引，然后计算有多少个 $j > i$ 满足 $a[j] < a[i]$，最后累计答案即可。
事实上，我们只需要这样做（设当前 $a[i] = x$）：
- 查询 $b[1 \ldots x - 1]$ 的前缀和，即为左端点为 $a[i]$ 的逆序对数量。
- $b[x]$ 自增 1；
原因十分自然：出现在 $b[1 \ldots x-1]$ 中的元素一定比当前的 $x = a[i]$ 小，而 $i$ 的倒序枚举，自然使得这些已在权值数组中的元素，在原数组上的索引 $j$ 大于当前遍历到的索引 $i$。
@@
用例子说明，$a = (4, 3, 1, 2, 1)$。
$i$ 按照 $5 \to 1$ 扫：
- $a[5] = 1$，查询 $b[1 \ldots 0]$ 前缀和，为 $0$，$b[1]$ 自增 $1$，$b = (1, 0, 0, 0)$。
- $a[4] = 2$，查询 $b[1 \ldots 1]$ 前缀和，为 $1$，$b[2]$ 自增 $1$，$b = (1, 1, 0, 0)$。
- $a[3] = 1$，查询 $b[1 \ldots 0]$ 前缀和，为 $0$，$b[1]$ 自增 $1$，$b = (2, 1, 0, 0)$。
- $a[2] = 3$，查询 $b[1 \ldots 2]$ 前缀和，为 $3$，$b[3]$ 自增 $1$，$b = (2, 1, 1, 0)$。
- $a[1] = 4$，查询 $b[1 \ldots 3]$ 前缀和，为 $4$，$b[4]$ 自增 $1$，$b = (2, 1, 1, 1)$。
所以最终答案为 $0 + 1 + 0 + 3 + 4 = 8$。
@@
注意到，遍历 $i$ 后的查询 $b[1 \ldots x - 1]$ 和自增 $b[x]$ 的两个步骤可以颠倒，变成先自增 $b[x]$ 再查询 $b[1 \ldots x - 1]$，不影响答案。两个角度来解释：
- 对 $b[x]$ 的修改不影响对 $b[1 \ldots x - 1]$ 的查询。
- 颠倒后，实质是在查询 $i \le j$ 且 $a[i] > a[j]$ 的数对数量，而 $i = j$ 时不存在 $a[i] > a[j]$，所以 $i \le j$ 相当于 $i < j$，所以这与原来的逆序对问题是等价的。
@@
如果查询非严格逆序对（$i < j$ 且 $a[i] \ge a[j]$）的数量，那就要改为查询 $b[1 \ldots x]$ 的和，这时就不能颠倒两步了，还是两个角度来解释：
- 对 $b[x]$ 的修改 影响 对 $b[1 \ldots x]$ 的查询。
- 颠倒后，实质是在查询 $i \le j$ 且 $a[i] \ge a[j]$ 的数对数量，而 $i = j$ 时恒有 $a[i] \ge a[j]$，所以 $i \le j$ **不相当于** $i < j$，与原问题 **不等价**。
如果查询 $i \le j$ 且 $a[i] \ge a[j]$ 的数对数量，那这两步就需要颠倒了。
另外，对于原逆序对问题，还有一种做法是正着枚举 $j$，查询有多少 $i < j$ 满足 $a[i] > a[j]$。做法如下（设 $x = a[j]$）：
- 查询 $b[x + 1 \ldots V]$（$V$ 是 $b$ 的大小，即 $a$ 的值域（或离散化后的值域））的区间和。
- 将 $b[x]$ 自增 $1$。
@@
原因：出现在 $b[x + 1 \ldots V]$ 中的元素一定比当前的 $x = a[j]$ 大，而 $j$ 的正序枚举，自然使得这些已在权值数组中的元素，在原数组上的索引 $i$ 小于当前遍历到的索引 $j$。