珂朵莉树/颜色段均摊
简介
珂朵莉树（Chtholly Tree），又名老司机树 ODT（Old Driver Tree）．起源自 CF896C．
这个名称指代的是一种「使用平衡树（std::set、std::map 等）或链表（std::list、手写链表等）维护颜色段均摊」的技巧，而不是一种特定的数据结构．其核心思想是将值相同的一段区间合并成一个结点处理．相较于传统的线段树等数据结构，对于含有区间覆盖的操作的问题，珂朵莉树可以更加方便地维护每个被覆盖区间的值．
实现（std::set）
结点类型
---|---
其中，`int v` 是你自己指定的附加数据．
`mutable` 关键字的含义是什么？
`mutable` 的意思是「可变的」，让我们可以在后面的操作中修改 `v` 的值．在 C++ 中，mutable 是为了突破 const 的限制而设置的．被 mutable 修饰的变量（mutable 只能用于修饰类中的非静态数据成员），将永远处于可变的状态，即使在一个 const 函数中．
这意味着，我们可以直接修改已经插入 `set` 的元素的 `v` 值，而不用将该元素取出后重新加入 `set`．
### 结点存储
我们希望维护所有结点，使得这些结点所代表的区间左端点单调增加且两两不交，最好可以保证所有区间的并是一个极大的连续范围．此处以 `std::set` 为例，用一个 `set<Node_t> odt;` 维护所有结点．
初始化时，向珂朵莉树中插入一个极长区间（如题目要求维护位置 11 到 𝑛n 的信息，插入区间 [1,𝑛 +1][1,n+1]）．
### split 操作
`split` 操作是珂朵莉树的核心．它接受一个位置 𝑥x，将原本包含点 𝑥x 的区间（设为 [𝑙,𝑟][l,r]）分裂为两个区间 [𝑙,𝑥)[l,x) 和 [𝑥,𝑟][x,r]，并返回指向后者的迭代器．
参考代码如下：
---|---
在不支持使用 auto 进行返回类型推导的编译器上，可以将函数的返回类型改为 set<Node_t>::iterator．
assign 操作
另外一个重要的操作：assign．用于对一段区间进行赋值．设将要对区间 [𝑙,𝑟][l,r]
赋值为 𝑣v．
首先，将区间 [𝑙,𝑟][l,r] 截取出来．依次调用 split(r + 1), split(l)，将此两者返回的迭代器记作 𝑖𝑡𝑟,𝑖𝑡𝑙itr,itl，那么 [𝑖𝑡𝑙,𝑖𝑡𝑟)[itl,itr) 这个迭代器范围就指向了珂朵莉树中 [𝑙,𝑟][l,r] 包含的所有区间．
然后，将原有的信息删除．std::set 有成员方法 erase，签名如同 iterator erase( const_iterator first, const_iterator last );，可以移除范围 [first; last) 中的元素．于是我们调用 odt.erase(itl, itr); 以删除原有的信息．
最后，插入区间 [𝑙,𝑟][l,r] 的新值．调用 odt.insert(Node_t(l, r, v)) 即可．
参考代码如下：
---|---
为什么需要先 `split(r + 1)` 再 `split(l)`？
1. `std::set::erase` 方法将使指向被擦除元素的引用和迭代器失效．而其他引用和迭代器不受影响．
2. `std::set::insert` 方法不会使任何迭代器或引用失效．
3. `split` 操作会将区间拆开．调用 `split(r + 1)` 之后 𝑟 +1r+1 会成为两个新区间中右边区间的左端点，此时 `split` 左区间，必然不会访问到 𝑟 +1r+1 为左端点的那个区间，也就不会将其拆开，删去 𝑟 +1r+1 为左端点的区间，使迭代器失效．反之，先 `split(l)`，再 `split(r + 1)`，可能会把 𝑙l 为左端点的区间删去，使迭代器失效．
### perform 操作
将珂朵莉树上的一段区间提取出来并进行操作．与 `assign` 操作类似，只不过是将删除区间改为遍历区间．
参考代码如下：
---|---
注意不应该滥用这样的提取操作，可能使得时间复杂度错误．见下文「复杂度分析」一栏．
实现（std::map）
相较于 std::set 的实现，std::map 的实现的 split 操作写法更简单．除此之外，其余操作与 std::set 并无二异．
结点存储
由于珂朵莉树存储的区间是连续的，我们不一定要记下右端点是什么．不妨使用一个 map<int, int> mp; 存储所有区间，其键维护左端点，其值维护其对应的左端点到下一个左端点之前的值．
初始化时，如题目要求维护位置 11 到 𝑛n 的信息，则调用 mp[1] = -1, mp[n + 1] = -1 表示将 [1,𝑛 +1)[1,n+1) 即 [1,𝑛][1,n] 都设为特殊值 −1−1，[𝑛 +1, +∞)[n+1,+∞) 这个区间当作哨兵使用，也可以对它进行初始化．
split 操作
参考代码：（第一份）
---|---
参考代码：（第二份）
---|---
这里使用了 std::map::insert 的重载 iterator insert( const_iterator pos, const value_type& value );，其插入 value 到尽可能接近正好在 pos 之前的位置．如果插入恰好发生在正好在 pos 之前的位置，那么复杂度是均摊常数，否则复杂度与容器大小成对数．
assign 操作
对于 assign 操作，我们需要把 [𝑙,𝑟 −1][l,r−1] 内所有区间左端点删除，再建立新的区间．
---|---
### perform 操作
---|---
实现（链表）
目前主流的实现是基于 set 来维护节点，但由于平均维护的区间个数很小，set 的优势并不明显．相比之下，链表（或数组）能更简洁地维护分裂与合并操作．
结点存储
---|---
### split 操作
---|---
在操作区间时，由于不能只维护区间的一部分，所以下面的操作进行之前都需要预先分裂区间，再完成相应操作．
---|---
### assign 操作
---|---
perform 操作
---|---
## 复杂度分析
### perform 以后立即对同一区间调用 assign
此时观察发现，两次 `split` 操作至多增加两个区间；一次 `assign` 将删除范围内的所有区间并增加一个区间，同时遍历所删除的区间．所以，我们所遍历的区间与所删除的区间数量成线性，而每次操作都只会增加 𝑂(1)O(1) 个区间，所以我们操作的区间数量关于操作次数（包括初始化）成线性，时间复杂度为均摊 𝑂(𝑚log𝑛)O(mlogn)，其中 𝑚m 为操作次数，𝑛n 为珂朵莉树中最大区间个数（可以认为 𝑛 ≤𝑚n≤m）．
### perform 以后不进行 assign
如果允许特殊构造数据，这样一定是能被卡掉的，只需要使珂朵莉树中有足够多的不同区间并反复遍历，就能使珂朵莉树的复杂度达到甚至高于平方级别．
如果要保证复杂度正确，必须保证数据随机．详见 [Codeforces 上关于珂朵莉树的复杂度的证明](http://codeforces.com/blog/entry/56135?#comment-398940)．更详细的严格证明见 [珂朵莉树的复杂度分析](https://zhuanlan.zhihu.com/p/102786071)．证明的结论是：用 `std::set` 实现的珂朵莉树的复杂度为 𝑂(𝑛loglog𝑛)O(nloglogn)，而用链表实现的复杂度为 𝑂(𝑛log𝑛)O(nlogn)．
## 习题
* [「Luogu 1840」Color the Axis](https://www.luogu.com.cn/problem/P1840)
* ~~[「SCOI2010」序列操作](https://www.luogu.com.cn/problem/P2572)~~ （该题目来源已添加 Hack 数据）
* [「SHOI2015」脑洞治疗仪](https://loj.ac/problem/2037)
* [「Luogu 4979」矿洞：坍塌](https://www.luogu.com.cn/problem/P4979)
* [「Luogu 8146」risrqnis](https://www.luogu.com.cn/problem/P8146)
## 扩展阅读
[ODT 的映射思想的推广 - 洛谷专栏 (luogu.com.cn)](https://www.luogu.com.cn/article/0mys9qkh)
## 参考资料和注释
* [Problem - 896C - Codeforces](https://codeforces.com/problemset/problem/896/C)（珂朵莉树的起源）
* [CF896C Willem, Chtholly and Seniorious 题解 - 洛谷专栏 (luogu.com.cn)](https://www.luogu.com.cn/article/gyxbe23s)（`std::set` 实现参考）
* [珂朵莉树的 map 实现 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/469794466)（`std::map` 实现参考）
* [题解 CF896C【Willem, Chtholly and Seniorious】- 洛谷专栏 (luogu.com.cn)](https://www.luogu.com.cn/article/umiw1fwp)（链表实现参考）
* [Codeforces Round #449 Editorial - Codeforces](https://codeforces.com/blog/entry/56135?#comment-398940)（关于珂朵莉树的复杂度的证明）
* [珂朵莉树的复杂度分析 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/102786071)（珂朵莉树的复杂度分析）
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/misc/odt.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/misc/odt.md "edit.link.title")
> __本页面贡献者：[StudyingFather](https://github.com/StudyingFather), [Tiphereth-A](https://github.com/Tiphereth-A), [Enter-tainer](https://github.com/Enter-tainer), [Marcythm](https://github.com/Marcythm), [CCXXXI](https://github.com/CCXXXI), [countercurrent-time](https://github.com/countercurrent-time), [H-J-Granger](https://github.com/H-J-Granger), [Henry-ZHR](https://github.com/Henry-ZHR), [Ir1d](https://github.com/Ir1d), [NachtgeistW](https://github.com/NachtgeistW), [ouuan](https://github.com/ouuan), [partychicken](https://github.com/partychicken), [AngelKitty](https://github.com/AngelKitty), [c-forrest](https://github.com/c-forrest), [caijianhong](https://github.com/caijianhong), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [dong628](https://github.com/dong628), [Early0v0](https://github.com/Early0v0), [ezoixx130](https://github.com/ezoixx130), [GavinZhengOI](https://github.com/GavinZhengOI), [GekkaSaori](https://github.com/GekkaSaori), [Gesrua](https://github.com/Gesrua), [Great-designer](https://github.com/Great-designer), [henrytbtrue](https://github.com/henrytbtrue), [hqztrue](https://github.com/hqztrue), [Konano](https://github.com/Konano), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [LovelyBuggies](https://github.com/LovelyBuggies), [lychees](https://github.com/lychees), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [mingyEx](https://github.com/mingyEx), [P-Y-Y](https://github.com/P-Y-Y), [Peanut-Tang](https://github.com/Peanut-Tang), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [sshwy](https://github.com/sshwy), [SukkaW](https://github.com/SukkaW), [Suyun514](mailto:suyun514@qq.com), [TrisolarisHD](mailto:orzcyand1317@gmail.com), [WAAutoMaton](https://github.com/WAAutoMaton), [weiyong1024](https://github.com/weiyong1024), [Xeonacid](https://github.com/Xeonacid), [yanboishere](https://github.com/yanboishere), [yaner-here](https://github.com/yaner-here), [ZnPdCo](https://github.com/ZnPdCo)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用