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 是函数式查询中，对应的查询表达式
```

看完文章有啥想法

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

目录