前言
- 珂朵莉树(Chtholly Tree),又名老司机树(Old Driver Tree),起源自 CF896C Willem, Chtholly and Seniorious 。
- 严格来说,珂朵莉树这种想法是基于数据随机的颜色段均摊,而不是一种数据结构,可作为一些题目的暴力做法(因此原题被分到了暴力数据结构的标签),在随机数据下一般效率较高。
基础知识
- 珂朵莉树常用来解决区间推平操作,核心思想是将值相同的区间合并成一个节点并保存到
set
里。 - 修改时再将区间分裂开进行操作。
- 随机数据下区间加、区间推平、区间求和用
set
实现的珂朵莉树的时间复杂度为 \(O(n \log \log n)\) ,而用链表实现的珂朵莉树的时间复杂度为 \(O(n \log n)\) 。证明建议参考 Codeforces 上关于珂朵莉树的复杂度的证明 | 珂朵莉树的复杂度分析 。
代码实现
- 保存节点
-
定义一个结构体
node
记录每个值 \(col\) 相同的一段区间 \([l,r]\) 。点击查看代码
struct node { int l,r; mutable int col; bool operator < (const node &another) const { return l<another.l; } }; set<node>s;
-
为方便随时修改已经插入到
set
里的元素的 \(col\) 而不用将这个元素先取出再重新加入set
,我们让 \(col\) 被 C++ 关键字mutable
修饰,使其处于可变状态。mutable
只能用于修饰类中的非静态数据成员。
-
- 初始化
init
-
不做讲解。
点击查看代码
void init(int n,int a[]) { s.clear(); for(int i=1;i<=n;i++) { s.insert((node){i,i,a[i]}); } }
-
- 分裂
split
-
将原先包含 \(pos\) 的区间 \([l,r]\) 分裂成两部分 \([l,pos-1],[pos,r]\) 并返回后者的迭代器。
点击查看代码
set<node>::iterator split(int pos) { set<node>::iterator it=s.lower_bound((node){pos,0,0}); if(it!=s.end()&&it->l==pos) { return it; } it--; if(it->r<pos) { return s.end(); } int l=it->l,r=it->r,col=it->col; s.erase(it); s.insert((node){l,pos-1,col}); return s.insert((node){pos,r,col}).first; }
-
假设我们当前找到了 \(it\) 这个位置,有三种情况。
- 第一,这个区间以 \(pos\) 开头,直接返回 \(it\) 即可。
- 第二,找到的区间比正好包含 \(pos\) 的区间大一点点;第三, \(pos\) 太大了,超过了最后一个区间的右端点。不妨先把 \(it\) 向前挪一个位置,判断 \(it\) 的右端点是否比 \(pos\) 小,若成立说明与第三种情况对应,返回 \(s\) 的尾迭代器,否则说明 \(it\) 包含了包含 \(pos\) 的区间,一分为二后删除原区间 \(it\) 并插入两个新区间 \([l,pos-1],[pos,r]\) 。
-
又因为
.insert()
返回值的第一关键字就是插入位置的迭代器,直接返回即可。- 关于
.insert()
返回值的详细信息建议参考 cppreference 。
- 关于
-
接下来对于 \([l,r]\) 的区间操作都能转化到
set
上 \([split(l),split(r+1)-1]\) 的操作。
-
- 推平
assign
-
把整个
set
中需要合并的区间全部删除再重新插入一个区间即可。 -
使用
.erase(first,last)
来辅助我们进行删除(区间为左闭右开 \([first,last)\) )。点击查看代码
void assign(int l,int r,int col) { set<node>::iterator itr=split(r+1),itl=split(l); s.erase(itl,itr); s.insert((node){l,r,col}); }
-
为避免因
.erase()
导致的迭代器失效问题,先执行split(r+1)
再执行split(l)
。- 若顺序颠倒可能导致
split(l)
得到的迭代器在split(r+1)
的erase
过程中时效从而导致 \(RE\) 。
- 若顺序颠倒可能导致
-
其他操作同理。
-
- 修改
update
/ 询问query
- 以区间加、区间求和为例。
点击查看代码
```cpp void update(int l,int r,int val) { set::iterator itr=split(r+1),itl=split(l); for(set ::iterator it=itl;it!=itr;it++) { it->col+=val; } } int query(int l,int r) { set ::iterator itr=split(r+1),itl=split(l); int ans=0; for(set ::iterator it=itl;it!=itr;it++) { ans+=it->col*(it->r-it->l+1); } return ans; } ```
- 以区间加、区间求和为例。