主席树 学习笔记

[也许更好的阅读体验](https://www.cnblogs.com/ConanKID/p/15733435.html)。 --- ~~为什么又要写学习笔记啊~~ --- 前置知识：权值线段树。 首先利用权值线段树求集合的 Kth 是挺简单的一个事情。相当于一个二分的操作。 现在需要考虑的问题是区间静态 Kth，即给定一个序列 $a$，多次询问一个区间 $[l,r]$ 中第 $k$ 小的数。 还是考虑权值线段树上二分。设当前节点为 $p$，统计 $[l,r]$ 中落在 $p$ 的左儿子所代表的区间内的数的数量 $x$。若 $x\ge k$，那么证明答案一定在左半区间里，直接向左儿子走。否则令 $k$ 减去 $x$，然后向右儿子走。 问题转化为如何快速求出落在一个节点所代表区间内的数的数量。 考虑建出 $n$ 棵线段树。对于 $1$ 到 $n$ 中的每一个 $i$，都单独建一棵权值线段树，存储把 $[1,i]$ 中的每一个 $a$ 插入线段树后的结果。同时对于每棵线段树，定义 $cnt_p$ 表示落在节点 $p$ 代表区间内的数的数量。这样求上面那个东西的时候就只需要把线段树 $r$ 上的 $cnt$ 与线段树 $l-1$ 相减即可。 但是仍然有问题：这样做空间会爆炸。 继续分析发现，线段树 $i$ 与线段树 $i-1$ 相比，只多插入了一个数，至多只更改了 $\log SIZE$ 个节点（$SIZE$ 表示值域）。因此只需要新建 $\log$ 个节点即可。 这里剽一张 OI-Wiki 上的图。 ![此处输入图片的描述][1] 红色表示新建的节点。 这样每次插入操作最多新建 $\log$ 个节点，空间复杂度做到了 $O(n\log n)$。 时间复杂度 $O(n\log n)$。 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int n, m, len; int a[maxn], ind[maxn], rt[maxn]; struct PresidentTree { #define mid (l + r >> 1) int ls[maxn << 5], rs[maxn << 5], sum[maxn << 5]; int cnt; int build(int l, int r) { int k = ++cnt; if (l == r) return k; ls[k] = build(l, mid); rs[k] = build(mid + 1, r); return k; } int update(int k, int l, int r, int val) { int dir = ++cnt; ls[dir] = ls[k]; rs[dir] = rs[k]; sum[dir] = sum[k] + 1; if (l == r) return dir; if (val <= mid) ls[dir] = update(ls[k], l, mid, val); else rs[dir] = update(rs[k], mid + 1, r, val); return dir; } int query(int l, int r, int p, int q, int val) { if (l == r) return l; int x = sum[ls[q]] - sum[ls[p]]; if (val <= x) return query(l, mid, ls[p], ls[q], val); else return query(mid + 1, r, rs[p], rs[q], val - x); } } t; void discrete() { memcpy(ind, a, sizeof(a)); sort(ind + 1, ind + 1 + n); len = unique(ind + 1, ind + 1 + n) - ind - 1; for (int i = 1; i <= n; i++) a[i] = lower_bound(ind + 1, ind + 1 + len, a[i]) - ind; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; discrete(); t.build(1, len); for (int i = 1; i <= n; i++) rt[i] = t.update(rt[i - 1], 1, len, a[i]); for (int i = 1; i <= m; i++) { int l, r, k; cin >> l >> r >> k; cout << ind[t.query(1, len, rt[l - 1], rt[r], k)] << endl; } return 0; } ``` 这玩意儿就是主席树。一个妙妙的数据结构。 --- 几道习题： - [P3567 [POI2014]KUR-Couriers][2] - [P4587 [FJOI2016]神秘数][3] --- 没有了。 [1]: https://oi-wiki.org/ds/images/persistent-seg.png [2]: https://www.luogu.com.cn/problem/P3567 [3]: https://www.luogu.com.cn/problem/P4587