[Dr.Lib]Note:Data Structures – 主席树 via 函数式线段树

偶然间翻PDF时看到了FHQ神犇的WC论文……看了一遍没记住什么……除了函数式编程其他也……就那样吧……顺手把CLJ的论文也看了一遍……//可持久化做法很多,函数式是种比较科学的实现……暴力复制、wzk树什么的就不说了……

然后函数式编程早就接触过但从来没有研究过TAT显然函数式线段树最成功的应用(之一?)就是主席树了……

函数式编程

修改元素是数据结构的一个基本操作,平常的实践中我们比较常见的就是直接改储存的值,而函数式编程中,我们从不去修改值,而是再定义一个。

对应在线段树操作中,我们每次修改值,都不会去修改任何节点,而是返回一棵新的树。

函数式Treap假想图 函数式线段树

图片来自范_wc2012

因为保证所有节点都不会被修改,所以我们可以重用未受影响的节点。显然,函数式线段树中,插入操作的时间、空间复杂度都是O(log n),其他操作与正常线段树无异。

主席树

主席树是一种利用函数式线段树维护数列的数据结构,一般用来解决区间第K大数问题。设数列长度为NN,数据范围为n,已离散化。

不支持修改的主席树(前缀和主席树)

……不支持修改的主席树在我的笔记中记为前缀和主席树…自己取的名字。。。

前缀和主席树由N棵线段树组成,第i棵Ti是对于[1,i]建一棵以序列里的值为下标,储存区间里出现该值的次数的线段树,也可以看作是Ti-1插入a[i]后的线段树。

注意到所有的树是同构(?)的,Ts-1和Tt可以直接相减得到T[s,t],在树上进行二分就可以得到区间K大值。

当然,所有的线段树都指函数式线段树。

代码:Via http://www.cnblogs.com/Rlemon/archive/2013/05/23/3094635.html 我自己码的实现惨不忍睹…这是和我的风格最接近的一个…以下是按我的笔记格式码的…

 

支持修改的主席树(树状主席树)

还记得当年学数据结构时如何维护带修改区间[s,t]的区间和吗?

树状数组,简单高效。既然我们维护的是一个线段树的前缀和,何不用树状数组维护呢?

脑补一棵树状数组,每个节点是一棵线段树 。修改时,我们仅需修改log n棵线段树即可。

//貌似只有我叫它树状主席树……正解是树状数组套主席树。

代码

 

临时建立节点的主席树

//待补完
参见clj的wc论文

CC BY-SA 4.0 [Dr.Lib]Note:Data Structures – 主席树 via 函数式线段树 by Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

5 thoughts on “[Dr.Lib]Note:Data Structures – 主席树 via 函数式线段树

  1. Pingback: POJ 2104 K-th Number 主席树 | 函数式线段树 | 亟隐

  2. 请问动态主席树中query(s,t,k);返回的是什么?加入我要查询第s个数到第t个数之中第k大的,那我应该如何输出?直接输出query(s,t,k)?为什么我做zoj2112发现不是这样的啊?怎么做都不对

发表评论

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.