主席树学习笔记

一些废话

今天下午老板让我这个刚学线段树一个月的菜鸡去学主席树，还自学。

我：认真的吗？

主席树定义

主席树是什么？

主席树，又称可持久化线段树。简单地说，就是在线段树每次update后，保留之前的版本。也就是说，保存若干次修改前的线段树。”保 留之前的版本”大概就是可持久化的意思（吧？）。这个有点像平时编辑器的撤销功能。

可持久化数据结构都是通过复用一些节点来节省空间。显然每次修改重新开一颗线段树超时炸空间。所以主席树尽量地使用原来的节点，必要的时候再创建节点。

对于一个普通的智商不至于外星人的OIer来说以上大概没有一句听懂了吧（或许是我太弱？

主席树的思想

模板

之前在学校OJ上用分块水过去的。

数据已经过加强，请使用主席树。同时请注意常数优化。

然而时限特别宽，一点都不卡常。

主席树具体怎么时限，结合全网通用的张图：

主席树和传统的线段树至少形态上有很大的不同。可以看到，很多节点共用了一个儿子。这就是”复用节点”在主席树中的实现。

每次插入节点，最多有 $logn$（$n$ 是区间长度）个节点被修改。

比如说，我们先建好一颗 $1\sim 7$ 区间的一颗空树。在主席树的每一个版本的线段树上，我们记录值在当前这个范围的数字有多少。

比如插入数字 $1$，树变成了这样：

但显然，不能每次插入都重新搞一颗树。这颗树和原来的空树，也就是上一个版本，有很多节点相同。

这些节点，就没必要重新创建。只需要重新创建 [$1$,$7$],[$1$,$4$],[$1$,$2$],[$1$,$1$]这四个点即可。

树应该是这样：（好丑啊，简直灵魂画师):

好了你已经了解了主席树的基本原理，让我们一起A了这道紫题板子吧。

简单的说就是，记录一个数组 $root[i]$，表示每个版本下主席树的根。每次修改创建一个新的根，将它在上一个版本的树中对应的位置（也就是表示区间和它相同的节点）$u$ 记录下来，如果要修改的点在左边，创建新的左儿子，递归左边，右儿子就是 $u$ 的右儿子。 反之递归右边，左儿子就是 $u$ 的左儿子。$sum[u]$ 表示节点 $u$ 的权值。

查询就很简单了，假设查询 $u\sim v$ 间的第 $k$ 小，那么主席树每个节点就是 $sum_u-sum_v$，在权值线段树上类似于二分查找这样搞一搞应该都会吧（

另外数这么大不离散化对得起良心吗

下面是你们最期待的东西。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define GetL(p) (ls[p] ? ls[p] : ls[p] = ++ nodetot)
#define GetR(p) (rs[p] ? rs[p] : rs[p] = ++ nodetot)

const int N = 2e5 + 5;
int n, a[N], b[N], Num[N];

struct Chairman_tree {//主 席 树
int sum[N << 5], root[N], ls[N << 5], rs[N << 5], nodetot, x;

inline void Update(int k, int p) {
x = p, update(root[k] = ++ nodetot, 1, n, root[k - 1]);
}
inline int Query(int l, int r, int k) {
return query(root[r], root[l - 1], 1, n, k);
}
void make_tree(int p, int x, int y) {
if (x == y) return;
make_tree(ls[p] = GetL(p), x, x + y >> 1),
make_tree(rs[p] = GetR(p), (x + y >> 1) + 1, y);
}

void update(int p, int l, int r, int root) {
if (l == r) {sum[p] = sum[root] + 1; return;}
int mid(l + r >> 1);
if (mid >= x) update(ls[p] = GetL(p), l, mid, ls[root]), rs[p] = rs[root];
else update(rs[p] = GetR(p), mid + 1, r, rs[root]), ls[p] = ls[root];
sum[p] = sum[ls[p]] + sum[rs[p]];
}

int query(int u, int v, int l, int r, int d) {
if (l == r) return l;
int mid(l + r >> 1), x(sum[ls[u]] - sum[ls[v]]);
if (d <= x) return query(ls[u], ls[v], l, mid, d);
else return query(rs[u], rs[v], mid + 1, r, d - x);
}
} Tree;

int main() {
int m;
scanf("%d%d", &n, &m);
Tree.make_tree(Tree.root[0] = Tree.nodetot = 1, 1, n);
for (int i(1); i <= n; ++ i) scanf("%d", a + i), b[i] = a[i];
std::sort(b + 1, b + n + 1);
for (int i(1); i <= n; ++ i)
Tree.Update(i, std::lower_bound(b + 1, b + n + 1, a[i]) - b);
while (~-- m) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", b[Tree.Query(l, r, k)]);
}
}