前言
- 珂朵莉树（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; } ```
- 以区间加、区间求和为例。