主席树设计与实现
一、主席树的一句话简介
1、主席树是可持久化线段树
2、可持久化技术用于将多棵树相同的部分复用、不同的部分分开构成一颗新树。
3、主席树的实际物理原型是多颗线段树。
二、区间第K大问题
1、设计上应当考虑，如果有了多颗线段树，应当怎么做这道题？
2、有了思路之后应当考虑，可持久化线段树的性质是什么样的，使得我们应当如何针对这种特殊的性质完成线段树的设计？
3、如何进行更新操作？
ans：
1、如果有多颗线段树，则每次插入新的元素建立一颗的线段树；在查找的时候，可以知道对于任意元素，有多少个元素小于等于给定元素。
2、想象可得，每个点的更新都将造成从最底部到根节点的一系列改变。因此，可得：根节点必然每次改变，且新的更节点可以带出新的其余替换节点。
3、考虑使用上一次的根节点的若干节点，在一路向下的过程中不断进行节点复制。这种写法可以相对优雅的完成主席树的更新。
题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1175
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 #define ll long long 6 #define idx(x) (lower_bound(mapp,mapp+n,x)-mapp) 7 8 9 const ll MAXN=1<<20; 10 11 int head[50233]; 12 int n,m; 13 class Node 14 { 15 public: 16 int l,r,number,lc,rc; 17 18 };Node tree[MAXN]; 19 int tree_cnt ; 20 int mapp[50233]; 21 int arr[50233]; 22 23 void build(int a,int b,int now) 24 { 25 tree_cnt ++ ; 26 tree[now].l = a; 27 tree[now].r = b; 28 tree[now].number = 0; 29 if(a == b-1)return ; 30 int mid = (a+b)/2; 31 tree[now].lc = tree_cnt; 32 build(a,mid,tree_cnt); 33 tree[now].rc = tree_cnt; 34 build(mid,b,tree_cnt); 35 } 36 37 void insert(int pos,int key,int times,int old) 38 { 39 40 int now = tree_cnt++; 41 int l = tree[old].l; 42 int r = tree[old].r; 43 44 tree[now].l = l; 45 tree[now].r = r; 46 tree[now].number = tree[old].number; 47 if(l == r-1) 48 { 49 tree[now].number += key; 50 return ; 51 } 52 int mid = (l+r)/2; 53 54 tree[now].lc = tree[old].lc; 55 tree[now].rc = tree[old].rc; 56 if(pos < mid) 57 { 58 tree[now].lc = tree_cnt; 59 insert(pos,key,times,tree[old].lc); 60 }else{ 61 tree[now].rc = tree_cnt; 62 insert(pos,key,times,tree[old].rc); 63 } 64 tree[now].number = tree[tree[now].lc].number + tree[tree[now].rc].number; 65 return ; 66 } 67 68 int search(int pos,int now) 69 { 70 int l = tree[now].l; 71 int r = tree[now].r; 72 if(l == r-1)return tree[now].number; 73 int mid = (l+r)/2; 74 int lc = tree[now].lc; 75 int rc = tree[now].rc; 76 if(mid <= pos)return tree[lc].number+search(pos,rc); 77 else return search(pos,lc); 78 } 79 80 int check(int a,int b,int num) 81 { 82 int cntt = search(num,head[b+1]); 83 cntt -= search(num,head[a]); 84 return cntt; 85 } 86 87 int bin_search(int a,int b,int l,int r,int num) 88 { 89 if(l == r-1)return mapp[r]; 90 int mid = (l+r)/2; 91 int cntt = check(a,b,mid); 92 if(cntt<num)return bin_search(a,b,mid,r,num); 93 else return bin_search(a,b,l,mid,num); 94 } 95 96 void init() 97 { 98 tree_cnt = 1; 99 head[0] = 1; 100 build(0,n,1); 101 for(int i=0;i<n;++i) 102 { 103 cin>>arr[i]; 104 mapp[i] = arr[i]; 105 }sort(mapp,mapp+n); 106 cin>>m; 107 for(int i=0;i<n;++i) 108 { 109 head[i+1] = tree_cnt; 110 insert(idx(arr[i]),1,i+1,head[i]); 111 } 112 for(int i=0;i<m;++i) 113 { 114 int a,b,c; 115 cin>>a>>b>>c; 116 cout<<bin_search(a,b,-1,n,b-a+2-c)<<" "; 117 } 118 } 119 int main() 120 { 121 cin.sync_with_stdio(false); 122 while(cin>>n)init(); 123 // build(0,233,1); 124 125 return 0; 126 }
三、动态的区间第K大
1、首先考虑可持久化数据结构的特点：可以让多个数据结构共享内存，因而优雅的实现需要发挥想象力的功能。
2、在试图考虑可持久化数据结构的设计方案的时候首先问自己一个问题：如果允许给能看见的每个节点加一个属于自己的数据结构，会怎么样呢？
For Example：多颗线段树、多个树状数组、多个伸展树、多颗字典树、多个KMP......等等（KMP部分是我随便想的，还没动手实现）
3、多数树形结构，在可持久化结构中“新建一棵树”只需要LOGN的从树根 开始建立一条到底部的新的支路“
4、在3的基础上，我们很容易想到，建立N颗主席树的话，只要接口设计得当就可以，套在树状数组上。
例题：csu2132 美食群岛
http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2132
题目大意：
1、给定一棵树，树上各个点具有权值。
2、考虑2个操作：
a、将树上某个节点a的权重改为给定值b。
b、查询由u到v的路径上，上下限为a,b的和。
解法：
1、首先考虑树链抛分，统计出各节点作为重链有限的dfs序，则一段重链上的数据可以在树状数组中连续排列。
2、之后考虑如果有N棵线段树，则将选段书的根节点排列至数组，则可以再logN的时间内查到当个节点的a,b之间的数字和。
3、考虑N棵线段树套在树状数组上，则可以再logn时间内做到查询，给定区间内，A,B的所有数字和。
4、因为不可能真的由足够大的内存开N棵线段树，所以实质上实现使用主席树。
5、考虑主席树的版本概念，考虑朴素树状数组：每个元素初始为0，则后续每个节点在本节点的基础上进行增加，则认为，每个位置的当前版本应当是其位置。
#include<iostream> #include<algorithm> #include<string.h> #include<math.h> #include<stdio.h> #include<vector> using namespace std; #define ll long long #define veci vector<int> #define pp pair<int,int> #define idx(x) (lower_bound(numbers,numbers+number_cnt,x)-numbers) int n,m; const ll MAXN=100233; int roots[MAXN]; class Node { public: int lc,rc,l,r,version; ll number; }; Node nodes[MAXN*30]; int root[MAXN]; int tree_cnt; void build(int a,int b) { // cout<<a<<" "<<b<<endl; int now = tree_cnt++; nodes[now].l = a; nodes[now].r = b; nodes[now].number = nodes[now].version = 0; if(a == b-1)return ; int mid = (a+b)/2; nodes[now].lc = tree_cnt; build(a,mid); nodes[now].rc = tree_cnt; build(mid,b); } void newNode(int num,int old,int ver) { nodes[num].l = nodes[old].l; nodes[num].r = nodes[old].r; nodes[num].number = nodes[old].number; nodes[num].lc = nodes[old].lc; nodes[num].rc = nodes[old].rc; nodes[num].version = ver; } void insert(int pos,int key,int now,int old,int ver) { int l = nodes[now].l; int r = nodes[now].r; if(l == r-1) { nodes[now].number+=key; return ; } int mid = (l+r)/2; if(pos < mid) { int tar = nodes[now].lc; int old_tar = nodes[old].lc; if(nodes[tar].version != ver) { newNode(tree_cnt,old_tar,ver); tar = nodes[now].lc = tree_cnt++; } insert(pos,key,tar,old_tar,ver); }else{ int tar = nodes[now].rc; int old_tar = nodes[old].rc; if(nodes[tar].version != ver) { newNode(tree_cnt,old_tar,ver); tar = nodes[now].rc = tree_cnt++; } insert(pos,key,tar,old_tar,ver); } int lc = nodes[now].lc; int rc = nodes[now].rc; nodes[now].number = nodes[lc].number + nodes[rc].number; } ll search_tree(int a,int b,int now) { int l = nodes[now].l; int r = nodes[now].r; // if(l == r)return nodes[now].number; if(a == l && b == r)return nodes[now].number; int mid = (l+r)/2; ll ret = 0; int lc = nodes[now].lc; int rc = nodes[now].rc; if(a<mid) { ret+=search_tree(a,min(mid,b),lc); if(b>mid)ret+=search_tree(mid,b,rc); }else ret+= search_tree(a,b,rc); return ret; } void insert_arr(int pos,int val,int key) { pos+=23; while(pos<n+24) { if(root[pos] == 0) { newNode(tree_cnt,0,pos); root[pos] = tree_cnt++; } insert(val,key,root[pos],root[0],pos); pos+=pos&(-pos); } } ll search_arr(int pos,int a,int b) { pos+=23; ll ret = 0; while(pos) { ret += search_tree(a,b,root[pos]); pos -= pos&(-pos); } return ret; } class Edge { public: int to,next; }; Edge edges[MAXN]; int edge_cnt; int G[MAXN*3]; void add_edge(int a,int b) { edges[edge_cnt].to = b; edges[edge_cnt].next = G[a]; G[a] = edge_cnt++; edges[edge_cnt].to = a; edges[edge_cnt].next = G[b]; G[b] = edge_cnt++; } class Order { public: char type; int a,b,c,d; }; Order orders[MAXN]; int arr[MAXN]; int numbers[MAXN*4]; int number_cnt; int child[MAXN]; int father[MAXN]; int arr_num[MAXN]; int arr_cnt = 0; int top[MAXN]; void dfs_child(int now,int fa) { child[now] = 1; father[now] = fa; for(int i = G[now];i!=-1;i = edges[i].next) { int tar = edges[i].to; if(tar == fa)continue; dfs_child(tar,now); child[now] += child[tar]; } } void dfs_devide(int now,int fa,int topp) { arr_num[now] = arr_cnt++; top[now] = topp; int maxx = 0; int pos = -1; for(int i = G[now];i!=-1;i = edges[i].next) { int tar = edges[i].to; if(tar == fa)continue; if(maxx < child[tar]) { maxx = child[tar]; pos = tar; } } if(pos!=-1)dfs_devide(pos,now,topp); for(int i=G[now];i!=-1;i = edges[i].next) { int tar = edges[i].to; if(tar == fa || tar == pos)continue; dfs_devide(tar,now,tar); } } ll jump(int u,int v,int a,int b) { ll ret = 0; if(arr_num[u] < arr_num[v])swap(u,v); while(u != v) { if(top[u] == top[v]) { ret += search_arr(arr_num[u],a,b); ret -= search_arr(arr_num[v],a,b); break; } ret += search_arr(arr_num[u],a,b); ret -= search_arr(arr_num[top[u]]-1,a,b); u = father[top[u]]; if(arr_num[u] < arr_num[v])swap(u,v); } ret += search_arr(arr_num[v],a,b); ret -= search_arr(arr_num[v]-1,a,b); return ret; } void init() { edge_cnt = 0; tree_cnt = 0; number_cnt = 0; arr_cnt = 0; root[0] = 0; for(int i=1;i<=n;++i) { G[i] = -1 ; root[i] = 0; scanf("%d",&arr[i]); numbers[number_cnt++] = arr[i]; }for(int i=n;i<n+25;++i)root[i] = 0; for(int i=1;i<n;++i) { int a,b; scanf("%d %d",&a,&b); add_edge(a,b); } dfs_child(1,0); dfs_devide(1,0,1); // cout<<"dfs_succ"<<endl; for(int i=0;i<m;++i) { char cc[5]; scanf("%s",cc); orders[i].type = cc[0]; // scanf("%c",&orders[i].type); if(orders[i].type == 'C') { scanf("%d %d",&orders[i].a,&orders[i].b); numbers[number_cnt++] = orders[i].b; }else{ scanf("%d %d %d %d",&orders[i].a,&orders[i].b,&orders[i].c,&orders[i].d); numbers[number_cnt++] = orders[i].c; numbers[number_cnt++] = orders[i].d; } } // cout<<"build_succ:"<<endl; sort(numbers,numbers+number_cnt); int point = 0; for(int i=1;i<number_cnt;++i) { if(numbers[i] != numbers[point]) { numbers[++point] = numbers[i]; } }number_cnt = point; build(0,number_cnt+2); for(int i=1;i<=n;++i) { insert_arr(arr_num[i],idx(arr[i]),arr[i]); } for(int i=0;i<m;++i) { if(orders[i].type == 'C') { int node = orders[i].a; int new_key = orders[i].b; int pos_arr = arr_num[node]; int old_key = arr[node]; insert_arr(pos_arr,idx(old_key),-old_key); insert_arr(pos_arr,idx(new_key),new_key); arr[node] = new_key; }else{ int u = orders[i].a; int v = orders[i].b; int a = orders[i].c; int b = orders[i].d; cout<<jump(u,v,idx(a),idx(b)+1)<<" "; } } } int main() { while(cin>>n>>m)init(); return 0; } /********************************************************************** Problem: 2132 User: RIKKA Language: C++ Result: AC Time:4304 ms Memory:105628 kb **********************************************************************/