主席树|HDU4417（主席树）主席树|数据结构

前言：今天刚学的主席树，附上博客：主席树
个人觉得这篇文章写的非常好。
认识：主席树就是对于序列 1...n 的每一个前缀都构造一颗线段树来维护所要求的值。也就是说主席树实际上就是 n 棵线段树。那么为什么不会 MLE ？这个下面再说。
先说一个经典的问题：静态区间第 k 大？（求区间 [l,r] 之间第 k 大的元素。无修改）

那么对于序列的前缀，需要知道 [1,l?1] 和 [1,r] 这两个区间内数的情况。
在每一个前缀建立的线段树中，线段树维护的是 [p,q] 这个区间内共有多少个数，注意这里的 p,q 不是我们的初始序列的位置，而是初始序列的的值，（一开始看的时候这里一直搞混，理解这里的话，主席树就比较好理解了）。大多数时候数不是连续的，这个时候离散一下就好了。
这里就出现了一个很好的性质：每一棵线段树维护的区间是一样的，每一个节点都是一样的（当然他们的节点值肯定不同，不然怎么玩?）。这个性质就可以保证节点维护的 sum 的加减运算不会出问题。
这个时候查询 [l,r] 之间的第 k 小，那么在序列 [1,l?1] 和序列 [1,r] 这两棵线段树之间维护。假设 rt[i] 表示 [1,i] 的根节点。那么第一次查询 tree[tree[rt[r]].ls].sum?tree[tree[rt[l?1]].ls].sum>k 的时候，就在 [l,mid] 这棵子树里面找，否则就在 [mid+1,r] 这棵子树里面找。做相应的改变即可。
这样时间复杂度很好算 o(nlogn)

下面来说一下为什么不会 MLE ?

比较两个前缀 [1,i?1] 和 [1,i] ，发现只是多了一个 a[i] 这个数，其他的都没有变化。
这个时候如果能够在 [1,i?1] 的线段树上经过小修小补就能完成该有多好啊？
实际上是可以的，如果这两个区间维护的是一棵线段树，那么这就是一个简单的区间修改的操作，但是这里我们还需要保存 [1,i?1] 的线段树下来。
就一个数 a[i] ，其实 a[i] 对一棵线段树的多少个区间产生了影响？ logn 个区间。这个时候只需要把改变过的 logn 的区间重新再新建一个节点，保存新的 [1,i] 线段树就可以了。此时发现绝大多数节点都实现了公用的功能。
这个时候就会得出一棵主席树的空间复杂度是 o(nlogn) 级别的，因为两棵相邻的线段树之间绝大多数节点都是公用的。也可以这样说，每次建立一棵新的线段树只相当于新增了 logn 个节点。

结论
时间复杂度： o(nlogn)
空间复杂度： o(nlogn)
【主席树|HDU4417（主席树）】下面贴一下这题的代码：（模板题）

#include using namespace std; typedef long longLL; typedef vector VI; typedef pair PII; #define FOR(i,x,y)for(int i = x; i < y; ++ i) #define IFOR(i,x,y) for(int i = x; i > y; -- i) #define pbpush_back #define mpmake_pair #define fifirst #define sesecondconst int maxn = 100010; int n,m,a[maxn],b[maxn]; map mat; struct Tree{ int ls,rs,sum; }tree[maxn*20]; int rt[maxn],tot; int build(int l,int r){ int o = tot++; tree[o].sum = 0; if(l == r)return o; int mid = (l+r)>>1; tree[o].ls = build(l,mid); tree[o].rs = build(mid+1,r); return o; }int update(int x,int l,int r,int lt,int v){ int o = tot++; tree[o] = tree[lt]; tree[o].sum += v; if(l == r)return o; int mid = (l+r)>>1; if(x <= mid)tree[o].ls = update(x,l,mid,tree[lt].ls,v); elsetree[o].rs = update(x,mid+1,r,tree[lt].rs,v); return o; }int query(int i,int j,int x,int l,int r){ if(l == r)return tree[i].sum - tree[j].sum; int mid = (l+r)>>1,ret = 0; if(x <= mid)ret += query(tree[i].ls,tree[j].ls,x,l,mid); else{ ret += tree[tree[i].ls].sum - tree[tree[j].ls].sum; ret += query(tree[i].rs,tree[j].rs,x,mid+1,r); } return ret; }void debug(int o,int l,int r){ if(l == r){printf("%d:%d ",l,tree[o].sum); return; } int mid = (l+r) >> 1; debug(tree[o].ls,l,mid); debug(tree[o].rs,mid+1,r); }int main(){ freopen("test.in","r",stdin); int T,tCase = 0; scanf("%d",&T); while(T--){ printf("Case %d:\n",++tCase); scanf("%d%d",&n,&m); FOR(i,1,n+1)scanf("%d",&a[i]),b[i] = a[i]; sort(b+1,b+n+1); int sz = unique(b+1,b+n+1)-b-1; FOR(i,1,sz+1)mat[b[i]] = i; tot = 0; rt[0] = build(1,sz); FOR(i,1,n+1)rt[i] = update(mat[a[i]],1,sz,rt[i-1],1); /* FOR(i,1,n+1){ debug(rt[i],1,sz); printf("\n"); } */ FOR(i,0,m){ int l,r,h; scanf("%d%d%d",&l,&r,&h); r ++; l ++; int k = upper_bound(b+1,b+sz+1,h)-b-1; //printf("r:%d l:%d k:%d ",r,l,k); if(k)printf("%d\n",query(rt[r],rt[l-1],k,1,sz)); elseprintf("0\n"); } } return 0; }