wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数据结构

线段树

线段树单点修改

线段树区间修改

可持久化线段树

树链剖分

平衡树

FHQ-Treap

[[ item.c ]]

可持久化线段树

## 主席树
###  区间第k小

假设有序列 $$A = \left<a_1, a_2, \cdots, a_n \right> = \left<-2, -6, 12, 3 \right>$$ 如何找区间第 k 小？

先将序列离散化成 $$[2, 1, 4, 3]$$，`for i = [1, n]`
	**对每一个`i`都建一棵区间 $$[1,i]$$ 的线段树**，这样在每个$$i$$上查询$$[1, i]$$的第$$k$$小，复杂度$$O(\log n)$$
	对于第$$i$$棵线段树，可以考虑在第$$i-1$$棵线段树上做修改
	![](/media/content_img/wsegTree-01.jpg)
	
*  定义主席树**节点权值**，在区间$$[l, r]$$中有多少个元素？
   > 注意到第$$i$$棵线段树和第$$j \ (i < j)$$棵线段树结构完全一样，区别仅仅是权值不同

根据**前缀和**，询问$$[L, R]$$，`tr[R] - tr[L-1]` 就表示$$[L, R]$$中有多少个元素
	> 实际上`tr[P] = tr[R]-tr[L-1]`也可以看作一棵线段树，结构一样，权值为对应点权值相减
	
*  这样就等于在 `tr[P]` 这棵线段树中找第 $$k$$ 小，利用二分思想
   如果`tr[P].left`的元素**个数**$$\geqslant k$$，递归在`tr[P].left`中找第$$k$$小
   否则，令$$k' = k- \text{cnt}(tr[P].left)$$，在`tr[P].right`中找第$$k'$$小
   
   > 另外，怎么保证**函数式做差**得到的线段树`tr[P] = tr[R] - tr[L-1]`恰好对应区间 $$[L, R]$$ 呢？
   注意到线段树维护**元素个数**，这样对于线段树$$i$$，只要保证
   $$[1,\cdots, i]$$ 中的点全部都有对应的值，$$[i+1,\cdots,n]$$ 中点未被插入，值是空的
   
**对线段树进行可持久化**
综上分析可以发现，上述算法时间复杂度很好，但是空间复杂度是$$O(n^2)$$的
![](/media/content_img/wsegTree-02.jpg)
注意到第$$i-1$$棵线段树到第$$i$$棵线段树，只有**加粗部分**不一样
加粗部分即**发生修改的路径**，只需要存储**修改路径**上的节点就可以了

**[K-th number](https://www.spoj.com/problems/MKTHNUM/en/)**
**[第 K 大数](https://vjudge.net/problem/SPOJ-MKTHNUM)**

主席树需要保存树**历史版本的根的指针**，这里用`ver[i]`表示第`i`个版本树的根的**编号**

> 主席树如何维护序列？
   和线段树类似，把主席树节点保存在`vector<Node> nd` 中

序列$$a_i$$对应第$$i$$个**版本**的线段树，它的根节点编号是`ver[i]`
（实际上，根节点是`nd[ ver[i] ]`，可以遍历这棵树了）

* 主席树维护序列`a[1...n]`，执行`insert(pid, l, r, pos, f)`
  其中`pid`表示**历史版本**，`l, r`表示**线段树节点对应区间**，`pos`是**叶节点**的值
  `f`是映射规则，将`pid`这棵线段树修改得到`nid`，$$nid = f(pid)$$，即函数式线段树映射
	
  `for i = [1, n]` 遍历序列，基于第$$i-1$$个**版本**的线段树执行**插入**$$a_i$$
 
*  在`ver[i-1]`中找到 $$a_i$$ 对应的**叶子结点**`mp[ a[i] ]`（离散化之后对应的值）
   （方法和普通线段树差不多，根节点 `ver[i-1]`表示区间$$[1, n]$$，往下递归）

*  实际上，`ver[i-1]`的根节点到叶节点形成一条**路径**$$path$$，对于`ver[i]`，
从根节点到叶节点路径需要**更新**为$$path^{\prime}$$，实际上主席树执行映射$$path^{\prime} = f(path)$$

对应地，路径上每一个点对应更新，`nd[ nid ].info = f( nd[ pid ].info )`
   如果叶节点`pos`在左区间，递归更新 `nd[nid].l` 左子树**指针**，否则更新右子树**指针**
   （将指针指向一个新建出来的节点，这样每次更新只新建了$$O(\log n)$$个节点）

> 主席树如何求区间$$[l, r]$$第$$k$$大元素？
  注意到**插入**节点的时候，节点**计数器**`cnt`，
  从叶子结点到根节点路径上，所有点的`cnt += 1`

* 主席树区间查询

一般指查询第$$[l, r]$$第$$k$$大，根据之前的分析
  针对`nd[ ver[r] ] - nd[ ver[l-1] ]`，即 **两棵线段树做差**结果来查询
  两个指针**同步遍历**线段树`nd[lid], nd[rid]`，同步找叶子结点
  
*  和普通`BST`不一样的是，我们需要对节点做**运算**，比如 `op(nd[rid], nd[lid])`
   > 这里**左儿子**的元素个数为`cnt`
   实际上`cnt`统计了**左儿子+其子树**的节点个数
   
   由此记 **`count = nd[ nd[rid].l ].cnt - nd[ nd[lid].l ].cnt`**（两个指针要**同步**遍历）
   如果 `count >= k`，那么往左子树递归找第 `k` 大
   否则往右子树递归找第 `k-count` 大

### 主席树算法实现
#### 模版定义

```bash
template<class S, class F, S (*upd)(F, S), S (*e)()
				class T, int MAXN> wseg_tree
```
* `S info` 是主席树维护的信息的数据类型

* `F f` 是**算子**的数据类型，比如第$$i-1$$个版本更新到$$i$$，对应路径上的点都加上`5LL`
   那么 `(F f)` 对应为 `(F f) = (long long   5LL)`，这个算子是如何赋值的呢？
   可以在**构造函数**中给算子赋值，比如
   `wseg_tree<ll, ll, ..., > tr(a, 5LL)`
   
*  `upd(F f, S x)`是函数式线段树映射，比如 `ver[i-1] -> ver[i]` 更新的时候，
   路径上的点都要**更改**，假设`ver[i-1]`的点为`x`
   ```bash
   ver[i-1] --> ver[i]
   x  ---> upd(f, x)
   ```
   举个例子，比如统计一个点及其子树点的个数`cnt`，可以定义
   `ll upd(ll f, ll x)  { return x+f; }`
   `f` 这个算子的值同样可以在构造函数中初始化，`wseg_tree<ll, ll, ...> tr(a, 1LL)`
   
*  `e()` 权值线段树中，`info`信息的初始值

*  `class T` 是原始数据类型，比如主席树维护 `A[1...n]`，`T`就是`A`的数据类型

*  `MAXN`是主席树节点数量，一般取 `n<<5`

#### 构造函数，插入与查询
```bash
wseg_tree(const vector<T>& a, F f)
```
*  `a` 是原始数据，`a[1...a.size()-1]`
   对应的线段树根节点的**编号**为 `ver[1, 2, ..., a.size()-1]`，`ver[0]`是哨兵
   
*  每一棵树的根节点维护区间 `[1, _n] = [1...idx]`，其中`idx`是离散化之后节点的个数

*  `f` 为算子的值，比如给每个节点都加上 `9LL`，那么 `F f` 对应为 `9LL`

```bash
int insert(int pid, int l, int r, int pos, F f)
```
*  函数返回值是新建节点的**编号** `nid`

*  `pid` 是**历史版本**，`nid`就是基于这个历史版本`pid`进行修改得到的

*  `l, r` 是主席树节点表示的区间，比如根节点就是 `[1, _n]`
   > 注意这里的 `_n` 是离散化之后节点的个数
   
*  `pos` 是叶子结点的值，一般是离散化之后的值
   比如插入`a[i]`，那么 `pos = mp[ a[i] ]`

*  `f` 是更新所用到的**算子**

```bash
int queryK(int lid, int rid, int l, int r, int K)
```

`lid, rid` 为查询区间的左右端点**对应的线段树**，它们的根节点**编号**
   比如查询 `[L, R]`，那么要执行 $$tr(R) - tr(L-1)$$，可以取
   `lid = ver[L-1], rid = ver[R]`
   
*  `l, r` 是线段树节点所表示的区间，比如根节点对应 `[1, _n]`

## 主席树的应用
### 区间小于等于 k 的数有多少
**[HDU4417](http://acm.hdu.edu.cn/showproblem.php?pid=4417)**
**[Super Mario](https://vjudge.net/problem/HDU-4417)**

**问题描述**
给定一个序列 $$a_1, \cdots, a_n$$，给定 $$m$$ 个询问，每个询问
`l r k`，查询区间 $$[l, r]$$ 内 $$\leqslant k$$ 的整数有多少个

**算法分析**
先来看一个问题，对于第$$i$$棵线段树，它的某个**叶子结点**$$x$$有哪些信息？

> 线段树`ver[i]`，只维护了**前缀** $$[a_1, \cdots, a_i]$$ 中的所有数
  考虑权值，从 $$x$$这个叶节点往根节点**追溯**
  
>  如果**一直从左边往上**追溯到点$$u$$，那么点$$u$$维护了前缀$$a[1, i]$$中
权值在$$[1, x]$$区间内点的个数

>  如果在追溯的时候，存在**右边往上**的路径，那么点$$u$$维护了一些权值 $$> x$$ 的点

由此，对区间 $$[l,r]$$ 查询 $$\leqslant k$$ 的节点个数
可以检查函数式线段树 $$tr(r) - tr(l-1)$$，具体来说
*  将 `k` **离散化**成叶子结点 `x`，从根节点递归找到叶节点`x`

*  如果 `x <= mid`，意味着当前区间还有一部分数可能权值 $$\geqslant x$$，继续递归左子树寻找

*  如果 `x > mid`，那么当前区间**左子树覆盖的所有点权值都**$$< x$$
   （实际上，左子树维护权值在 $$[1, mid]$$ 的点的个数）
   所以 `ans += nd[ nd[r].l ].cnt - nd[ nd[l-1].l ].cnt`
   
   还有一部分 $$mid < [\cdots] \leqslant x$$ 的数，递归到右子树查询
   两部分加起来就是答案
   
### 统计区间内有多少个不同数
**问题描述**
给定序列$$a_1, \cdots, a_n$$ 和 $$m$$ 个询问，每次询问给定
`l r k`，对区间 $$[l, r]$$ 中的数，只统计**它们第一次出现**的位置
要求回答区间内有多少个不同的数？假设区间有 $$K$$ 个不同的数，
那么这$$K$$个不同数的下标为 $$p_1, p_2, \cdots , p_K$$，需要回答
```math
p_{\lceil \frac{K}{2} \rceil}
```
是多少？即第 $$\lceil\frac{K}{2} \rceil$$ 个数的**下标**

**算法分析**
> 传统主席树能不能做？

**注意**，这里只需要求出**下标**，具体值多少我们并不需要求，考虑下标作为叶节点建主席树

> 扫描序列，对于$$a_i$$，我们在叶节点 $$i$$ 处$$+1$$，这样行不行呢？
  很明显，如果区间内 $$a_i = a_j$$，那么同一个数就被统计了$$2$$次
  （当然区间不同数，用莫队是可以做的）
  
> 那么用函数式线段树，对于$$[l, r]$$，用 `tr[r] - tr[l-1]` 可不可以呢？  
   如果 $$[l, r]$$ 中$$x$$出现了$$1$$次，$$[1, l-1]$$中$$x$$也出现了一次
   用`tr[r] - tr[l-1]`岂不是`[l, r]`中$$x$$没有出现过？明显不符合啊
   
考虑能不能扫描序列的时候，对所有元素，只统计它**第一次出现**的位置，
并对相应**位置**的叶节点值$$+1$$，其他出现的位置，叶节点值不增加

可以**倒序扫描**序列，$$i+1 \to i$$ 的时候，如果`cnt[ a[i] ] = 0`
那么 `ver[i] = add(ver[i+1], i, 1)`，表示在`ver[i+1]`个版本基础上，叶节点`i`处`+1`
否则，`ver[i] = add(ver[i+1],  i,  1)`，然后 `ver[i] = add(ver[i], cnt[ a[i] ], -1)`，然后记 `cnt[ a[i] ] = i`

> 这里很容易搞错，首先`ver[i]`基于`ver[i+1]`版本执行$$i$$处单点增加
   如果之前`cnt[a[i]]`有值，那么就说明`ver[i]`**加太多了，要删掉**
   此时的修改是基于`ver[i]`版本的修改

> 这样的话，`ver[i]` 这棵线段树和它的叶节点表示什么？

`ver[i]`这棵线段树中只保存在 $$[i\cdots, n]$$ 出现的所有数（$$[1,i-1]$$没有保存下来）
其次，每个数只记录了它**第一次出现的位置**
> 比如$$x$$在$$[i, n]$$第一次出现的位置是$$p$$，那么叶节点$$p$$到根，路径上的点的值都`+1`

那么，区间$$[l, r]$$中有多少个数就很容易求了
在`ver[l]`这棵线段树中，执行传统的线段树区间查询，找到表示`[l, r]`区间的节点
节点的`info`就是答案

怎么求第  $$k = \lceil\frac{K}{2} \rceil$$ 个数？

注意到我们只要知道**下标**即可，考虑从`ver[l]`的根节点往下递归
递归到哪个叶节点（因为此时叶节点表示下标），这个叶节点的值就是答案

递归过程就是标准的二分，如果左子树的值`info >= k`，那么查询左子树
否则，在右子树中查询`k-info`

## 主席树标记永久化

**什么是标记永久化**
标记永久化，就是对区间$$[l, r]$$修改的时候，只在**最终节点**$$[l, r]$$打上标记
其他时候**不压标记，不清空标记**，那么递归的**中间节点**呢？

对于中间节点区间$$[L, R]$$，注意到$$[l, r] \subseteq [L, R]$$
（目标区间$$[l,r]$$一定是中间节点区间的子区间），所以递归中间节点只需要更改**部分**值
`mapping(f, nd[pid].info, PII [l, r], PII [li, ri])`，其中`[li, ri]`是目标区间
对于中间节点区间，只需要对**其中的一段** `[max(l, li),  min(r, ri)]` 做映射 `f( nd[pid].info )`

> 由此可见标记永久化有局限性，只能维护可以线性变化的序列
   比如让区间都加上`v`，可以在`[L, R]`中**只考虑变化的那一段**`[l, r]`，`sum += v * (r-l+1)`
   而并非所有的变化都可以满足这个特征

递归到**目标节点`nid`时**，打上懒标记 `lazy[nid] = composition(f, lazy[nid])`
   
**如何解决查询问题**
查询目标区间$$[li, ri]$$，需要统计**从根节点到终点的累计变化量**，用`accu`来表示
这可以一边递归一边累计

如果当前节点`u`**不是**目标区间，那么将懒标记`lazy[u]`**复合到**`accu`上
如果是**目标区间**，将当前的`accu`作用到节点上
执行 `mapping(accu, nd[u].info, [l, r], [li, ri])`
> 此时 `[l, r] = [li, ri]`

**特别注意**
> 根据版本`ver[pid]`来建线段树`ver[nid]`的时候，懒标记要**复制**
   `lazy[nid] = lazy[pid]`

**[HDU4348](http://acm.hdu.edu.cn/showproblem.php?pid=4348)**
**[To the moon](https://vjudge.net/problem/HDU-4348)**

**问题描述**
给定$$a_1, \cdots, a_n$$，给定$$m$$个操作，并且有时间戳
`C L R d` 将 `[L, R]` 所有数都`+d`，时间戳`t += 1`，只有这个操作会改变`t`
`Q L R` 查询区间和
`H L R t` 查询时间`t`的历史区间和
`B t` 返回时间`t`，`t` 之后的操作全部清空

**算法分析**
对每个时间戳建一个版本的线段树，按主席树的方法来处理

值得注意的是，因为有清空操作，所以可以将`t`作为一个**全局版本指针**
每一次`C`操作，`t += 1`，并且基于`ver[t-1]`的版本执行`ver[t] = insert(ver[t-1], ....)`
查询历史版本的区间和，就直接在`ver[t]`上执行查询
至于`B`操作，直接更改版本指针`t`即可

**标记永久化算法实现**
```bash
template<class S, S (*e)(), class T, S (*op)(S, S),
	class LZ, S (*mapping)(LZ, S, PII, PII), LZ (*composition)(LZ, LZ), LZ (*id)()>
```

*  `class S` 需要维护的数据类型，比如区间最小值，区间和，类型是`long long sum`
    那么声明的时候`S = long long`，维护的信息在`Node`中对应`info`字段
	
*  `S e()`，是维护的`info`的初始值，比如求最小值时候$$+\infty$$，求区间和`e() = { return 0; }`

*  `class T` 是原始数据的数据类型，比如根据序列`a[1...n]`来建线段树
   `a`是`long long`类型，那么`T = long long`
   
*  `S op(S, S)`对应传统线段树的`pull`方法，`info = op(left.info, right.info)`
   左右子树`info`的复合，就是当前节点的`info`
   
*  `class LZ` 对应**懒标记的数据类型**，比如将一个区间都加上`long long d`
   那么`LZ = long long`
   值得注意的是，可以理解为懒标记`LZ lazy`就是**映射**，如果一个节点有懒标记，一般需要
   `nd[nid].info = lazy( nd[pid].info )`，即将原来的 $$\text{info} \to \text{lazy(info)}$$
   
*  `mapping(LZ, S, PII seg, PII ask)`，`LZ`为懒标记类型，`S`为维护信息的数据类型
   `seg`是当前节点对应的区间`[l, r]`，`ask`是**目标节点**对应的区间`[li, ri]`
   
*  `LZ (*composition)(LZ, LZ)` 定义了**懒标记映射的复合**，比如，将一个区间都加上`d`
   那么**复合**的意思是，一个节点可能会**累计**加上$$d_1, d_2, \cdots$$
   `LZ comp(LZ f, LZ g)  { return f+g; }`
   
*  `LZ id()` 是单位映射，$$\text{id}(x)=x$$，比如将所有数都加上$$d$$，对应此时 `id()  { return 0; }`

> 需要注意的细节，就是`ver[pid] -> ver[nid]`的时候，需要记得复制懒标记
`lazy[nid] = lazy[pid]`

**成员函数**
*  `ver[0] = build(1, _n)`，有时候需要一开始根据整个序列把线段树建出来
   作为初始版本
   
*  `ver[i] = insert(ver[i-1], 1, _n, li, ri, f)`，在`ver[i-1]`版本的基础上
   对`[li, ri]`区间所在节点的`info`，执行映射 `info -> f( info )`，`f`是算子
   实际上执行`info = mapping(f, info, [l, r], [li, ri])`
   其中`[l, r]`是遍历路径上**中间节点**对应的区间，`[li, ri]`是**最终**区间
   
*  `res = query(ver[t], 1, _n, li, ri, id() )`
   在第`t`个**版本**的线段树中，找到`[li, ri]`对应的区间，并且返回区间对应的`info`
   实际上，因为标记永久化，我们还需要**累计路径上所有标记**（来模拟压标记的过程）
   累计统计时候的初始值对应单位变换`id()`
   
## 主席树树上查询
**[Count on a tree](https://www.spoj.com/problems/COT/en/)**
**[SPOJ COT](https://vjudge.net/problem/SPOJ-COT)**

**问题描述**
给定 $$N$$ 个节点的树，每个节点有一个权值，有 $$m$$ 个询问，每个询问
`u v k`，询问$$u\to v$$ （包括$$u, v$$）路径第$$k$$小的点的权值

**算法分析**
> 能不能通过`dfs`序将本问题转换成序列问题？`dfs`序能求出什么？

如果求树上某个节点的**子树**（包括这个节点）的第$$k$$小，是可以考虑`dfs`序的
因为`dfs`序能保证**子树**对应序列中**一段连续区间**
用`l[u]`表示第一次访问`u`的时间戳，`r[u]`表示回溯完的时间戳，那么$$[l_u, r_u]$$ 就对应子树所在的区间

> 本题求$$u \to v$$树链上的第$$k$$小，并不能用`dfs`序
   因为`u -> LCA -> v`路径在`dfs`序上**不一定连续**
   
这里解决树链问题，用**树上差分 + 主席树**

记$$f(u)$$为$$u$$到根节点路径上点的个数，那么$$u \to v$$路径上实际的点个数为
$$f(u) + f(v) - 2f(\text{lca}) + \text{lca}$$，如果记$$\text{lca}$$的父亲节点为$$\text{plca}$$
点的个数实际上是 $$f(u) + f(v) - f(\text{lca}) - f(\text{plca})$$

**算法实现**
在树上建主席树和依据序列建主席树略有不同，需要在`dfs(u, pa)`，第一次访问`u`节点的时候
`ver[u] = tr.insert(ver[pa], 1, _n, mp[ a[u] ])`，即根据父节点的版本，创建当前节点

> 注意，树上建主席树，会用到**函数式线段树查询**

比如本例中
```bash
int g(array<int, 4> arr) {
    auto [t1, t2, t3, t4] = arr;
    return tr.nd[ tr.nd[t1].l ].cnt + tr.nd[ tr.nd[t2].l ].cnt 
        - tr.nd[ tr.nd[t3].l ].cnt - tr.nd[ tr.nd[t4].l ].cnt;
};
```
$$f(u)+f(v)-f(lca)-f(plca)$$ 实际上用到了`4`个参数，调用的时候
```bash
int res = tr.query<4, g>(Arr{ver[u], ver[v], ver[lca], ver[plca]}, 
            1, tr._n, k);
			
template<int M, int (*g)(array<int, M>)>
    int query(array<int, M> arr, int l, int r, int K)
	
// M是函数式线段树查询，需要用到的参数数量，本例 M = 4
// g 是函数式查询中，对应的查询表达式
```

## 主席树随机化哈希
**[Codeforces Round 837 (Div. 2) F. Hossam and Range Minimum Query](https://codeforces.com/contest/1771/problem/F)**
**问题描述**
给定一个长度为$$n$$的数组$$a$$，以及$$q$$个询问$$[L, R]$$
询问区间中出现次数为奇数的数，**最小的一个**，如果不存在，返回`0`，强制在线

### 随机化算法
区间第`1`小，不难想到用主席树，那么如何处理**出现次数为奇数**这个条件呢？
不难想到可以用**异或操作**作为条件判断，那么大致算法如下

建主席树的时候，可以考虑离散化，`a  -> mp(a)`，离散化之后建主席树
这里对于离散化之后的点，给一个随机化哈希值`hs( mp(a) ) = mrand()`，并且把这个值写入主席树节点的`info`中
哈希值异或和为`0`，说明区间所有数都出现偶数次，否则就存在出现次数为奇数的数

> 那么`info`中的值怎么维护呢？实际上只需要自定义`upd`操作即可

```bash
unsigned int upd(rnd, info) {
	return rnd ^ info;
}
主席树自顶向下，边插入边修改
基于历史版本修改的过程，保存了区间所有数的异或

和普通线段树对比，普通线段树需要 pull(ls, rs) 操作，把子区间所有信息都统计起来
主席树，基于 ver[i-1] -> ver[i] 版本的时候，新插入一个数，是自顶向下的
从上到下，从最大的区间到子区间，节点都会添加这个新的 info
所以主席树，一般来说需要用 upd(f, info) 来维护信息
ver[i-1] -> ver[i] 是怎么变化的？添加了哪些数？
```

> 怎么查询呢？

和主席树查询大同小异，对于区间`[L, R]`，我们考虑`nd[R].info ^ nd[L-1].info`，这就是这个区间内所有数的异或和了
先检查左半边，如果左半边的异或和为`1`，就走左半边，否则走右半边
左半边的异或和也不难求，`nd[ nd[R].l ].info ^ nd[ nd[L-1].l ].info`

### 随机化哈希算法实现
```bash
wseg_tree {
	// 其他代码忽略

template<typename T>
    void build(const vector<T> &a, map<T, int> &mp, vector<T> &rm, map<int, int> &rnd) {
        int tot = 0;

for (int i = 1; i < (int)a.size(); i++) mp[a[i]] = 0;
        for (auto &p : mp) {
            p.second = ++tot, rm[tot] = p.first;
        }
        for (int i = 1; i < (int)a.size(); i++) {
            auto x = mp[a[i]];
            if (!rnd.count(x)) rnd[x] = mrand();
        }

_n = tot;
        vector<Node> ((int)a.size()<<5, Node{}).swap(nd);
        vector<int> ((int)a.size()+5, 0).swap(ver);

for (int i = 1; i < a.size(); i++) {
            ver[i] = insert(ver[i-1], 1, _n, mp[a[i]], rnd[ mp[a[i]] ]);
        }
    }
	
	// 以下是查询
	// // 查询满足 f(r) - f(l-1) = ??? 条件的，min_left 位置
    template<int (*f)(S, S)>
    int min_left(int lid, int rid, int l, int r) {
        if (l >= r) {
            if (f( nd[lid].info, nd[rid].info ) == 0) return -1;
            return l; 
        }
        int mid = (l + r) >> 1;
        int val = f( nd[ nd[lid].l ].info, nd[ nd[rid].l ].info );

if (val != 0) return min_left<f>(nd[lid].l, nd[rid].l, l, mid);
        else return min_left<f>(nd[lid].r, nd[rid].r, mid+1, r);
    } 
}

// 定义 f 运算
int upd(int rnd, int info) {
    return rnd ^ info;
}
int id() {
    return 0;
}

int f(int infol, int infor) {
    return infol ^ infor;
}

void solve() {
    map<int, int> mp, rnd;
    vector<int> rm(n+5, 0);
    wseg_tree<int, int, upd, id> tr(0);
    tr.build(a, mp, rm, rnd);
	
	// query [l, r]
	 auto res = tr.min_left<f>(tr.ver[l-1], tr.ver[r], 1, tr._n);
	 ans = rm[res]
}
```

## 主席树算法实现
### 区间第 k 大
```bash
template<class S, class F, S (*upd)(F, S), F (*id)()>
class wseg_tree {
public:
    struct Node {
        S info;
        int cnt;
        int l, r;
    };

int idx = 0;
    int _n = 0;

// 这里的 _n 表示根节点的值域范围 [1, _n]
    // 也就是离散化之后，tr 叶子结点表示的数是 [1, 2, ..., _n]
    // ver[i] 表示第 i 个版本的树的根的编号

vector<Node> nd;
    vector<int> ver;

explicit wseg_tree(int n) : _n(n) {
        idx = 0;
        nd = vector<Node> (_n<<5, Node());
        ver = vector<int> (_n+5, 0);
    }

// 构造函数，用于数组 a 的离散化，同时构建函数式线段树
    // f 表示从旧版本，pid -> nid 过程中，node[nid] = f( node[pid] )
    template<typename T>
    void build(const vector<T> &a, map<T, int> &mp, vector<T> &rm, F f) {
        idx = 0;
        rm = vector<T> ((int)a.size()+5, T{}), mp.clear();

for (int i = 1; i < (int)a.size(); i++) mp[a[i]] = 0;
        for (auto &p : mp) {
            p.second = ++idx, rm[idx] = p.first;
        }

_n = idx;
        nd = vector<Node> ((int)a.size()<<5, Node{});
        ver = vector<int> ((int)a.size()+5, 0);

for (int i = 1; i < a.size(); i++) {
            ver[i] = insert(ver[i-1], 1, _n, mp[a[i]], f);
        }
    }

// 0 是哨兵节点
    int insert(int pid, int l, int r, int pos, F f) {
        if ( !(l <= pos && pos <= r) ) return 0;

const auto &pre = nd[pid];
        int nid = ++idx;
        nd[nid] = Node{ upd(f, pre.info), pre.cnt+1, pre.l, pre.r };

if (l >= r) return nid;

int mid = (l + r) >> 1;
        if (pos <= mid) nd[nid].l = insert(pre.l, l, mid, pos, f);
        else nd[nid].r = insert(pre.r, mid+1, r, pos, f);

return nid;
    }

// [l, r] 是待查询区间，线段树的叶子结点满足 l >= r
    // 叶子结点 x，离散化后的数对应的就是 x

int queryK(int lid, int rid, int l, int r, int K) {
        if (l >= r) return l;
        
        const auto &le = nd[lid];
        const auto &ri = nd[rid];
        int cnt = nd[ri.l].cnt - nd[le.l].cnt;
        int mid = (l + r) >> 1;

if (K <= cnt) return queryK(le.l, ri.l, l, mid, K);
        else return queryK(le.r, ri.r, mid+1, r, K-cnt);
    }
};

ll upd(ll f, ll x) {
    return f + x;
}

ll id() {
    return 0LL;
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

map<ll, int> mp;
    vector<ll> rm(n+5, 0);

wseg_tree<ll, ll, upd, id> tr(n);
    tr.build<ll>(a, mp, rm, id());

while (q--) {
        int l, r, k;
        cin >> l >> r >> k;

auto ans = tr.queryK(tr.ver[l-1], tr.ver[r], 1, tr._n, k);
        printf("%lld\n", rm[ans]);
    }
}
```
### 区间小于等于 k 的数的个数
**[数数](http://oj.daimayuan.top/problem/464)**
```bash
    // 查询 [l, r] >= x 的数有多少个
    int query(int lid, int rid, int l, int r, int x) {
        if (l >= r) return nd[rid].cnt - nd[lid].cnt;

int mid = (l + r) >> 1;
        auto le = nd[lid], ri = nd[rid];

if (x <= mid) return query(le.l, ri.l, l, mid, x);
        else {
            int res = 0;
            int cnt = nd[ri.l].cnt - nd[le.l].cnt;
            res += cnt;
            res += query(le.r, ri.r, mid+1, r, x);
            return res;
        }
    }
```
### 查询区间有多少个不同的数
这时一般根据**下标**来建主席树，并且`mp[ a[i] ] = i`，记录`a[i]`最后一次出现的位置
主席树`build`的时候，首先`ver[i] = insert(ver[i-1], i, 1)`
如果`mp[ a[i] ]`存在，那么要删掉之前的，`ver[i] = insert(ver[i], mp[a[i]], -1)`（插入一个$$-1$$即可）

```bash
    template<typename T>
    void build(const vector<T> &a, map<T, int> &mp, vector<T> &rm, F f) {
        idx = 0;
        rm = vector<T> ((int)a.size()+5, T{}), mp.clear();

_n = (int)a.size();
        nd = vector<Node> ((int)a.size()<<5, Node{});
        ver = vector<int> ((int)a.size()+5, 0);

for (int i = 1; i < a.size(); i++) {
            ver[i] = insert(ver[i-1], 1, _n, i, f);
            if (mp[a[i]]) ver[i] = insert(ver[i], 1, _n, mp[a[i]], -1*f);
            mp[a[i]] = i;
        }
    }
	
	ll ask(int lid, int rid, int l, int r, const int li, const int ri) {
        if (li <= l && r <= ri) return nd[rid].info - nd[lid].info;
        
        int mid = (l + r) >> 1;
        const auto &L = nd[lid], &R = nd[rid];

ll res = 0;
        if (li <= mid) res += ask(L.l, R.l, l, mid, li, ri);
        if (ri > mid) res += ask(L.r, R.r, mid+1, r, li, ri);

return res;
    }
```

### 标记永久化
```bash
ll mapping(ll f, ll info, PII seg, PII ask) {
    auto [l, r] = seg;
    auto [li, ri] = ask;

if (li == -1) return info + 1LL * f * (r-l+1);
    
    return info + 1LL * f * (min(r, ri) - max(l, li) + 1);
}

ll comp(ll f, ll g) {
    return f + g;
}

lazy_wsegtree {
	//...
    int insert(int pid, int l, int r, const int li, const int ri, F f) {
        int nid = ++idx;
        nd[nid] = Node{ mapping(f, nd[pid].info, {l, r}, {li, ri}), nd[pid].l, nd[pid].r };
        lazy[nid] = lazy[pid];

if (li <= l && r <= ri) {
            lazy[nid] = comp(f, lazy[nid]);
            return nid;
        }

int mid = (l + r) >> 1;
        if (li <= mid) nd[nid].l = insert(nd[pid].l, l, mid, li, ri, f);
        if (ri > mid) nd[nid].r = insert(nd[pid].r, mid+1, r, li, ri, f);

return nid;
    }

// {-1, -1} 是哨兵，表示我们到达目标区间了
    S query(int nid, int l, int r, const int li, const int ri, F accu) {
        if (li <= l && r <= ri) {
            S res = mapping(accu, nd[nid].info, {l, r}, {-1, -1});
            return res;
        }
        accu = comp(lazy[nid], accu);
        int mid = (l + r) >> 1;

S res = S(0);
        if (li <= mid) res += query(nd[nid].l, l, mid, li, ri, accu);
        if (ri > mid) res += query(nd[nid].r, mid+1, r, li, ri, accu);
        return res;
    }
};
```

### 主席树树上查询
```bash
wseg_tree {
    typedef array<int, 4> Arr;
    int queryK(const Arr &arr, int l, int r, int K) {
        if (l >= r) return l;

int mid = (l + r) >> 1;
        auto [u, v, lca, plca] = arr;
        // printf("dbg: %d %d %d %d\n", u, v, lca, plca);
        int cnt = nd[nd[u].l].cnt + nd[nd[v].l].cnt - nd[nd[lca].l].cnt - nd[nd[plca].l].cnt;
        
        Arr narr;
        (K <= cnt) ? (narr = {nd[u].l, nd[v].l, nd[lca].l, nd[plca].l}) 
                : (narr = {nd[u].r, nd[v].r, nd[lca].r, nd[plca].r});

if (K <= cnt) return queryK(narr, l, mid, K);
        else return queryK(narr, mid+1, r, K-cnt);
    }
};

void solve() {
	//....
    auto dfs = [&](auto &dfs, int u, int pa) -> void {
        dep[u] = dep[pa] + 1;
        tr.ver[u] = tr.insert(tr.ver[pa], 1, tr._n, mp[ a[u] ], id());
        for (auto v : G[u]) {
            if (v == pa) continue;
            up[v][0] = u;

dfs(dfs, v, u);
        }
    };
	
	// 输入 u, v, k，查询 u -> v 路径第 k 大
	auto lca = LCA(u, v);
    auto plca = up[lca][0];
    array<int, 4> arr = {tr.ver[u], tr.ver[v], tr.ver[lca], tr.ver[plca]};

auto res = tr.queryK(arr, 1, tr._n, k);
    printf("%lld\n", rm[res]);
}
```

看完文章有啥想法

fogsail

看看其他评论功能

2023-06-23 19:16:46
点赞（0）回复（2）

zhangminchen @ fogsail

可以吧～

2023-06-23 19:17:07
点赞（0）回复（1）

zhangminchen @ zhangminchen

自己回复自己看看

2023-06-23 19:17:15
点赞（0）回复（0）
zhangminchen

试试看～

2023-06-23 19:01:51
点赞（0）回复（3）

zhangminchen @ zhangminchen

不错，考虑一下

2023-06-23 19:15:35
点赞（0）回复（2）

fogsail @ zhangminchen

支持一个啦啦

2023-06-23 19:16:27
点赞（0）回复（1）

fogsail @ fogsail

自己回复自己～

2023-06-23 19:16:34
点赞（0）回复（0）

算法小站

wiki 主题

数据结构

可持久化线段树

fogsail

zhangminchen @ fogsail

zhangminchen @ zhangminchen

zhangminchen

zhangminchen @ zhangminchen

fogsail @ zhangminchen

fogsail @ fogsail

目录