可持久化线段树
据说是某个HJT的人发明的所以叫主席树？
对于线段树而言.我们大多数写的均为区间线段树.
也就说是存的一个个的区间.
到达叶子节点表示的才是单独一个点的值.好像多数都是左闭右开的样子…
同时存在一种权值线段树的东西.
这个点与后面的左右儿子无关,只能单独记录点,每次节点都会\(++orz\)然后使用引用的骚操作改变其左右儿子.
很迷对不对.
但是主席树就是很多棵这个样的线段树.
权值线段树在查询的时候和\(Treap\)一样.需要判断当前节点的大小和要查询节点的值.
根据值左右递归.
\(Treap\)里面查询排名的时候,如果左子树没有满足要求的,就需要向右子树查询,前提是减去左子树和当前根节点对应的值.
这好像跟线段树没什么关系
但是线段树里面存的是一段数字区间出现的次数,所以需要离散化一下出现的数字.
How to 离散化？
|
1 2 3 4 |
memset(sorta,a,sizeof(a)); sort(sorta+1,sorta+1+n); //再之后的操作直接二分或者lower_bound也是可以的. |
单纯说建立\(n\)棵线段树的话,这是会\(MLE\)的
但是实际上单点修改的话,其实我们只用修改其中的一条链就可以了.
那么实际上我们需要的是\(log_2n\)的时间空间.
也就是说我们只用保留原来的节点,然后多加一条链,就完成了单点修改的主席树的操作.
主席树的每棵节点保存的市一颗线段树.
其中维护的区间相同,结构相同,保存的信息不同.
所以对于区间\([l,r]\)的操作.我们可以直接处理\([1-l-1]\)区间和\([1-r]\)区间.
最后区间\([l,r]\)不就是\(root[r]-root[l-1]\)
这样就可以求出区间中的数.
当然主席树是在一颗线段树上加链去链的.所以我们需要先新建一颗新的值都是0的线段树.
|
1 2 3 4 5 6 7 8 9 |
void build(int &o,int l,int r){ o=+orz; if(l==r) return; int M=(l+r)>>1; build(tr[o].lc,l,M); build(tr[o].rc,M+1,r); return; } |
因为是权值线段树,所以并不存在\(pushup\)的操作.
如果是我口胡的话会回来改的哼唧.
比如我们拿\(poj2104\)来说的话.
题意是要求我们求一个不定区间\([l,r]\)的第\(k\)大的值.
建树操作和离散化操作与之前一样,就不过多重复.
如何\(update()\)?
对于这个题目我们可以理解为,如果数组有序,排名第k个的就是答案.
原数组无序,我们可以通过结构体打标然后关键字排序再搞.
但是操作麻烦并且时间很凉.
对于主席树就可以
在所有的线段树中,是按照当前区间元素的离散值大小来储存的,在每一个节点,存的是这个区间每个元素出现的次数和.
这里主席树是干啥的？
是对原来的数列\([1-n]\)的每一个前缀\([1-i]\)建立一颗线段树,线段树中的每一个节点存在区间\([l,r]\)的数共有多少个.
然而我们要查找区间第\(k\)大的数字,我们可以直接判断区间内哪一个节点\(x\)内的出现数字的总和是\(k\),也就是找到了对应的\(x\)喽.
我们新建链是根据之前已经完好的树建的,而且跟前缀有关,所以我们存个数的时候也就是上一棵树的个数+1.
|
1 2 3 4 5 6 7 8 9 10 11 |
void update(int &o,int pre,int l,int r,int pos){ o=++orz; if(l==r)return; tr[o].lc=tr[pre].lc; tr[o].rc=tr[pre].rc; tr[o].sum=tr[pre].sum+1; int M=(l+r)>>1; (pos<=M)?update(tr[o].lc,tr[pre].lc,l,M,pos):update(tr[o].rc,tr[pre].rc,M+1,r,pos); return; } |
我们要\(update\)是要把离散后的元素插入.
所以上面离散化其实还没完…
|
1 2 3 4 5 |
for(int i=1;i<=n;i++){ int pos=lower_bound(sortb+1,sortb+1+n,a[i])-sortb; update(root[i],root[i-1],1,n,pos); } |
这个\(update\)并不带修改操作.
带修改操作的怎么办？
因为我们说的处理\([l,r]\)区间就用\([1\ -\ l-1]\)和\([1\ -\ r]\)区间加减就好了,修改操作是一样的.
那么区间查的时候和我们之前所想象的一样.
因为是离散过后的元素,所以最后查询完输出的时候需要再离散回来.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int query(int o,int pre,int l,int r,int x){ if(l==r) return l; int M=(l+r)>>1; int sum=tr[tr[pre].lc].sum-tr[tr[o].lc].sum; return (pos<=M)?query(tr[o].lc,tr[pre].lc,l,M,x):query(tr[o].rc,tr[pre].rc,M+1,r,x-sum); } while(m--){//m次操作. int l,r,x; printf("%d\n",sortb[query(root[l-1],root[r],1,n,x)]); } |
前面有说到,这里求区间第\(k\)大之所以可以判断当前节点与要查找的值做比较,是因为我们这里建的是一颗权值线段树,主席树大多数是权值线段树,但不是说没有区间线段树.
主席树的主席是很多棵形态完全相同的线段树.
既然形态完全相同,那么每个节点就可以做减法.
利用权值线段树求第\(k\)大的方法求,\(n\)个数求区间第\k(\)大.
相当于有\(n\)个权值线段树
例如.\([1,2,3]\),插入过程中会形成三棵树,里面存储的权值分别是\([1],[1,2],[1,2,3]\),最后求\([2,3]\)区间第\(k\)大就是第三棵树-第一棵树.
最后尽可能动态开点节省空间.
后面的树是根据之前的树建立的链.
所以我们先要建立一颗插入0个元素的线段树.
感觉一样的思路重复了好多遍QAQ
但是为什么总感觉欠了哪一点点没理解QAQ
带修改的区间第\(k\)大
- 如果我们按照原来的方式保存历史版本后,修改一个元素就得改后面依据这条链而建成的所有的链,这会导致\(TLE\)……
- \(root[i]\)表示的这颗线段树,保存的市从第一个元素开始插入到第\(i\)个元素后的数字区间.也就是说每次我们进行线段树区间相减的时候,我们是对两个前缀和\([1,l-1],[1,r]\)减的.
- 可以用树状数组来优化前缀和.这样我们仅需要\(log_2n\)的复杂度就可以让主席树支持单点修改.
- 但是我们用树状数组维护前缀和的话,插入原序列中一个一个元素在\(n\)棵空树上维护前缀和.会导致主席树没超空间,而树状数组超空间了…
树状数组动态开点么？别梦了…我们可以先对初始序列按照无修改的方式建好线段树后不再修改.对于每次修改,我们可以再另外\(n\)个线段树上维护前缀和,最后直接加在一起效果也是一样.最后就得到了支持了区间修改的主席树.
That’s All….
坑填满啦,该被水题爽了……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std ; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return ; } const int maxn = 100010; int n,m,orz,root[maxn],a[maxn],x,y,k,sortb[maxn]; struct node{int lc,rc,sum;}tr[maxn*40]; void build(int &o,int l,int r){ o=++orz; if(l==r) return ; int M=(l+r)>>1; build(tr[o].lc,l,M); build(tr[o].rc,M+1,r); return ; } void update(int &o,int pre,int l,int r,int pos){ o=++orz; tr[o].lc=tr[pre].lc; tr[o].rc=tr[pre].rc; tr[o].sum=tr[pre].sum+1; if(l==r) return ; int M=(l+r)>>1; (pos<=M)?update(tr[o].lc,tr[pre].lc,l,M,pos):update(tr[o].rc,tr[pre].rc,M+1,r,pos); return ; } int query(int o,int pre,int l,int r,int pos){ if(l==r) return l; int sum=tr[tr[pre].lc].sum-tr[tr[o].lc].sum; int M=(l+r)>>1; if(pos<=sum) return query(tr[o].lc,tr[pre].lc,l,M,pos); else return query(tr[o].rc,tr[pre].rc,M+1,r,pos-sum); } int main() { read(n),read(m); for(int i=1;i<=n;i++) read(a[i]); memcpy(sortb,a,sizeof(a)); sort(sortb+1,sortb+1+n); build(root[0],1,n); for(int i=1;i<=n;i++){ int pos=lower_bound(sortb+1,sortb+1+n,a[i])-sortb; update(root[i],root[i-1],1,n,pos); } while(m--){ int o,pos,x; read(o),read(pos),read(x); printf("%d\n",sortb[query(root[o-1],root[pos],1,n,x)]); } return 0; } |
区间修改的拖着拖着……
By:Wahacer
2017.12.26
17:34