treap模板(set,map,multiset, 可持久化treap)

全部模板链接


以前treap学得不怎么扎实,最近用重新温习了一下。
写法不同,它能实现set,map,multiset等不同的功能。
与STL相比增加的功能就是:

1.求第k大的数, 2.求一个数v是第几大的数   等等功能


学了能可持久化的treap

看了一下clj的可持久化数据结构研究论文。

做了一下UVA 12538,算是会了一点点了。

可持久化treap不用进行rotate操作,它有两个基本的操作

merge(a,b):把 treap<a>与treap<b>合并成treap<c>

 split(a,k):把treap<a>的前k个变成一个treap<b>,剩下的元素变成treap<c>

可以根据需要来选择是否实现可持久化, 如果不需要,那么就正常修改

如果需要可持久化,那么对于版本v变到版本v+1,操作所走过的路径要重新新建节点,

可以写一个copy()函数来方便新建。



treap模板(set,map,multiset, 可持久化treap)

上一篇:多DataTable合并为一个DataTable


下一篇:总结过去展望未来