珂朵莉树

珂朵莉树

珂朵莉树是一颗树,我们用集合来维护,c++中集合是红黑树,所以我们借助此集合来完成珂朵莉树。
我们将区间分段,那么各段有唯一的左端点,我们将左端点放入集合,当我们遍历集合的时候,我们就得到了我们要的序列,此时我们维护了结构,但未维护值,进一步发现我们可以使用map,用键值对来维护更多信息,键用来维护树的结构,值来维护序列的值。

split

因为我们要维护区间信息,所以我们需要操作split来提取区间,本质上提取区间为提取单点,这一点在splay中表现的很出色,当我们提取出左端点和右端点的时候,区间也就被提取出来了,如果提取位置x,在红黑树中我们二分到x的位置,若此处是一个区间[l,r],我们将此区间拆分为[l,x-1][x,r]即可。

assign

我们提取出区间,删掉这些节点然后,插入一个新的节点即可

add

我们提取出区间,暴力更新所有节点即可

sum

我们提取出区间,暴力计算所有节点,使用快速幂

kth

我们提取出区间,还是暴力

什么时候选择此数据结构

数据随机且含有区间赋值操作,此数据结构的操作可以在splay上实现,并维护更多信息,map法仅仅只是编码简单了很多。

例题

C. Willem, Chtholly and Seniorious

odt代码