【模板】主席树的学习

Kth number

划分树虽然可以做，但是代码不好记。

看某人blog学习了主席树的简单操作。

引用某大牛的话来解释一下主席树：

所谓主席树呢，就是对原来的数列[1..n]的每一个前缀[1..i]（1≤i≤n）建立一棵线段树，线段树的每一个节点存某个前缀[1..i]中属于区间[L..R]的数一共有多少个（比如根节点是[1..n]，一共i个数，sum[root] = i；根节点的左儿子是[1..(L+R)/2]，若不大于(L+R)/2的数有x个，那么sum[root.left] = x）。若要查找[i..j]中第k大数时，设某结点x，那么x.sum[j] x.sum[i 1]就是[i..j]中在结点x内的数字总数。而对每一个前缀都建一棵树，会MLE，观察到每个[1..i]和[1..i1]只有一条路是不一样的，那么其他的结点只要用回前一棵树的结点即可，时空复杂度为O(nlogn)。

——具体看代码（有详细注释）

1 #include <cstdio> 2 #include <algorithm> 3 #define lc son[now][0], l, mid 4 #define rc son[now][1], mid + 1, r 5 6 using namespace std; 7 8 const int N = 100000 + 5; 9 10 int T, n, q, tot; 11 int a[N], b[N], son[20 * N][2], sum[20 * N], rt[20 * N]; 12 //主席树第 i 棵树存的是 a[0] a[i] 的树（前缀和） 13 //主席树一个节点 sum 存的是当前线段所包含的数的个数。。晕。 14 //rt 是每一棵树的根节点编号 15 //a 保存原数组，b 保存排序后的数组 16 17 //注意 & 的使用 18 inline void build(int &now, int l, int r) 19 27 28 inline void update(int &now, int l, int r, int last, int x) 29 41 42 //因为每个节点存的是有多少个数在当前区间 43 //求区间 [1,3] 即求 rt[3] rt[0] 内的数 44 //可通过递归二分解决 45 inline int query(int s, int t, int l, int r, int x) 46 52 53 int main() 54 73 } 74 return 0; 75 }
View Code

Kth Number

——代码

1 #include <cstdio> 2 #include <algorithm> 3 #define debug puts("***********"); 4 5 const int MAXN = 100001; 6 int n, m, cnt; 7 int b[MAXN], root[MAXN]; 8 struct node 9 p[MAXN]; 12 struct pst 13 t[MAXN * 20]; 16 17 inline bool cmp(node x, node y) 18 21 22 inline void insert(int x, int &now, int l, int r) 23 32 33 inline int query(int x, int y, int k, int l, int r) 34 40 41 int main() 42 56 for(i = 1; i <= m; i++) 57 61 return 0; 62 }
View Code

上一篇：[luoguP1866]滑动窗口（单调队列）

下一篇：[Vijos1512] SuperBrother打鼹鼠 （二维树状数组）

---

主席树 模板 离散化