主席树

可持久化线段树

据说是某个HJT的人发明的所以叫主席树?


对于线段树而言.我们大多数写的均为区间线段树.

也就说是存的一个个的区间.

到达叶子节点表示的才是单独一个点的值.好像多数都是左闭右开的样子…

同时存在一种权值线段树的东西.

这个点与后面的左右儿子无关,只能单独记录点,每次节点都会\(++orz\)然后使用引用的骚操作改变其左右儿子.

很迷对不对.

但是主席树就是很多棵这个样的线段树.


权值线段树在查询的时候和\(Treap\)一样.需要判断当前节点的大小和要查询节点的值.

根据值左右递归.

\(Treap\)里面查询排名的时候,如果左子树没有满足要求的,就需要向右子树查询,前提是减去左子树和当前根节点对应的值.


这好像跟线段树没什么关系

但是线段树里面存的是一段数字区间出现的次数,所以需要离散化一下出现的数字.

How to 离散化?

单纯说建立\(n\)棵线段树的话,这是会\(MLE\)的

但是实际上单点修改的话,其实我们只用修改其中的一条链就可以了.

那么实际上我们需要的是\(log_2n\)的时间空间.

也就是说我们只用保留原来的节点,然后多加一条链,就完成了单点修改的主席树的操作.

主席树的每棵节点保存的市一颗线段树.

其中维护的区间相同,结构相同,保存的信息不同.

所以对于区间\([l,r]\)的操作.我们可以直接处理\([1-l-1]\)区间和\([1-r]\)区间.

最后区间\([l,r]\)不就是\(root[r]-root[l-1]\)

这样就可以求出区间中的数.


当然主席树是在一颗线段树上加链去链的.所以我们需要先新建一颗新的值都是0的线段树.

因为是权值线段树,所以并不存在\(pushup\)的操作.

如果是我口胡的话会回来改的哼唧.


比如我们拿\(poj2104\)来说的话.

题意是要求我们求一个不定区间\([l,r]\)的第\(k\)大的值.

建树操作和离散化操作与之前一样,就不过多重复.

如何\(update()\)?

对于这个题目我们可以理解为,如果数组有序,排名第k个的就是答案.

原数组无序,我们可以通过结构体打标然后关键字排序再搞.

但是操作麻烦并且时间很凉.

对于主席树就可以

在所有的线段树中,是按照当前区间元素的离散值大小来储存的,在每一个节点,存的是这个区间每个元素出现的次数和.

这里主席树是干啥的?

是对原来的数列\([1-n]\)的每一个前缀\([1-i]\)建立一颗线段树,线段树中的每一个节点存在区间\([l,r]\)的数共有多少个.

然而我们要查找区间第\(k\)大的数字,我们可以直接判断区间内哪一个节点\(x\)内的出现数字的总和是\(k\),也就是找到了对应的\(x\)喽.

我们新建链是根据之前已经完好的树建的,而且跟前缀有关,所以我们存个数的时候也就是上一棵树的个数+1.

我们要\(update\)是要把离散后的元素插入.

所以上面离散化其实还没完…

这个\(update\)并不带修改操作.

带修改操作的怎么办?

因为我们说的处理\([l,r]\)区间就用\([1\ -\ l-1]\)和\([1\ -\ r]\)区间加减就好了,修改操作是一样的.

那么区间查的时候和我们之前所想象的一样.

因为是离散过后的元素,所以最后查询完输出的时候需要再离散回来.


前面有说到,这里求区间第\(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….

坑填满啦,该被水题爽了……



区间修改的拖着拖着……


By:Wahacer

2017.12.26

17:34

发表评论

电子邮件地址不会被公开。 必填项已用*标注