珂朵莉树
fightinggg
11月 09, 2019
珂朵莉树
珂朵莉树是一颗树，我们用集合来维护，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