某科学的珂朵莉树
Charllote_ · · 算法·理论
更好的阅读体验
update
| 时间 | 修改 |
|---|---|
| 2025.8.15 | 改正函数返回值错误 |
珂朵莉树概述
见百度百科&bilibili 。
珂朵莉树又称老司机树（Chtholly Tree / Old Driver Tree）暴力数据结构，特别适用于处理区间赋值、区间修改等操作。该结构在随机数据下表现优异，尤其在处理大量区间操作时具有显著优势。
该数据结构最早在 Codeforces Round #394 (Div. 1) 的 C 题 CF-896C 中被提出，并因其题面中角色“珂朵莉”的名字而得名。在实际应用中，珂朵莉树常用于替代线段树或树状数组，在某些特定场景下实现更简洁、高效的代码逻辑。
前置知识
STL-set
简介
set 是 C++ STL 提供的标准关联容器，其核心特性包括元素唯一性和自动排序。底层基于红黑树（自平衡二叉搜索树）实现，这使得插入、删除和查找操作的时间复杂度均为
迭代器 —— set <T>::iterator
set 的迭代器是 const_iterator，不允许通过迭代器修改元素值（排除使用 mutable）。通过 begin() 和 end() 可获取正向迭代器（指向首元素和尾后位置），rbegin() 和 rend() 获取反向迭代器（指向尾元素和首前位置）。迭代器在插入 / 删除操作后不会失效（红黑树仅调整指针，不移动内存）。 迭代器使用方式与普通指针相同。迭代器支持两种操作为 const_iterator++、const_iterator--，分别指向前驱和后继。
查找 —— find()
find(value) 函数用于查找元素 value，返回指向该元素的迭代器；若不存在，返回 end()。时间复杂度为
set<int> s = {1, 3, 5};
auto it = s.find(3); // it 指向元素 3
if (it != s.end()) cout << *it; // 输出 3 插入 —— insert()
insert(value) 函数用于向 set 中插入元素 value，返回一个 pair<iterator, bool> 类型：
- iterator：指向插入元素的迭代器（若元素已存在，则指向原元素位置）。
- bool：插入成功标志（
true表示插入新元素，false表示元素已存在）。 时间复杂度为\Theta(\log n) （红黑树节点插入需平衡调整，仅涉及指针操作）。 示例：
set<int> s;
// 插入新元素，返回 {迭代器, true}
auto res1 = s.insert(3);
if (res1.second) cout << "插入成功: " << *res1.first; // 输出 3
// 插入重复元素，返回 {原元素迭代器, false}
auto res2 = s.insert(3);
if (!res2.second) cout << "元素已存在，当前值: " << *res2.first; // 输出 3 删除 —— erase()
set 提供三种删除方式：
- 按值删除：
erase(value)，删除所有值为value的元素（set 中最多一个），返回删除的元素个数（0 或 1）。 - 按迭代器删除：
erase(it)，删除迭代器it指向的元素，无返回值。 - 区间删除：
erase(first, last)，删除 [first, last) 区间内的元素，无返回值。 时间复杂度：均为\Theta(\log n) （红黑树节点删除仅需指针调整）。 示例：
set<int> s = {2, 5, 8};
s.erase(5); // 删除值为 5 的元素，s 变为 {2, 8}
auto it = s.find(2);
s.erase(it); // 删除迭代器指向的元素，s 变为 {8} 规定大小查找 —— lower_bound()
lower_bound(value) 返回指向第一个大于等于 value 的元素的迭代器；若所有元素均小于 value，返回 end()。时间复杂度为
set<int> s = {1, 4, 6, 9};
auto it = s.lower_bound(5); // 第一个 >=5 的元素是 6，it 指向 6
cout << *it; // 输出 6 正文
原理
珂朵莉树的核心思想是通过维护一个有序的区间集合（存储在 set 中），将整个数组划分为若干个值相同且连续的区间。每个区间用一个节点表示，包含左端点 l、右端点 r 和区间值 val。当需要对某个区间进行操作时，通过分裂（split） 操作将覆盖该区间的节点拆分成精确匹配的子区间，再进行修改或查询，最后通过合并（merge） 操作将相邻的相同值区间合并，以减少节点数量。 为何节省时间？
- 区间合并特性：在大量区间赋值操作下，数组会被划分成少量连续区间，使每次操作只需处理少数节点（而非逐个元素）。
- 随机数据优化：在随机数据中，区间操作后节点数量增长缓慢，单次操作的时间复杂度接近
\Theta(\log n) 。 - 简洁的实现：相比线段树，珂朵莉树代码量少，逻辑直观，减少了实现错误的可能性。
期望时间复杂度证明
珂朵莉树的效率依赖于区间赋值操作和随机数据分布。假设初始有
- 分裂（split）：通过
lower_bound定位区间，时间复杂度\Theta(\log m) （m 为当前节点数）。 - 区间操作：每次操作需分裂
O(1) 次，遍历O(k) 个节点（k 为操作区间覆盖的节点数）。在随机数据下，k 的期望为O(\log n) 。 - 总复杂度：对于
q 次操作，期望时间复杂度为O(q \log n) ，与线段树相当，但常数更小。
节点存储信息 —— ODT_node
珂朵莉树的每一个节点都存储了一段元素相同的区间，并把每一个节点按左端点从小到大扔进有序集即 set 中来方便操作。
struct ODT_node {
int l, r; // 区间的左右端点
mutable int val; // 区间的取值（由于可能修改所以使用 mutable）
bool operator < (const ODT_node x) const {return l < x.l;}
// 为使用是 set 需要重载运算符并按左端点排序
};建树操作 —— void build(int a[], int n)
void build(int a[], int n) 表示建一棵表示
void build(int a[], int n) {
int x = a[1], pos = 1;
// x 为值，pos 为一段连续的值的左端点
for (int i = 2; i <= n; i++) {
if (a[i] != x) {
t.insert({pos, i - 1, x});
pos = i; x = a[i];
// 找到不同的位置，插入节点
}
}
t.insert({pos, n, a[n]});
// 插入剩下的元素
}查找节点操作 —— set<ODT_node>::iterator find(int x)
set<ODT_node>::iterator find(int x) 表示查找包含
set<ODT_node>::iterator find(int x) {
auto it = t.lower_bound({x, 0, 0});
// 找出要分裂的节点的下一个节点
if (it == t.end() || it->l > x) it--;
// 找出要分裂的节点
return it;
}节点分裂操作 —— set<ODT_node>::iterator split(int x)
set<ODT_node>::iterator split(int x) 表示把一个包含
flowchart LR
A(l, r, val) --> D[(split x)]
D --> B(l, x - 1, val)
D --> C(x, r, val)具体过程为先二分得出需要分裂的节点，然后删除要分裂的节点，插入分裂后的两个节点。
set<ODT_node>::iterator split(int x) {
auto it = t.find(x);
// 找出要分裂的节点
if (it->l == x) return it;
// 如果要分裂的节点左端点就是 x，则不需要分裂
int l = it->l, r = it->r, val = it->val;
// 记录信息，防止之后的操作改变指针
t.erase(it); t.insert({l, x - 1, val});
return t.insert({x, r, val}).first;
// 删除要分裂的节点，插入分裂后的两个节点
}区间合并操作 —— set<ODT_node>::iterator merge(set<ODT_node>::iterator it, bool dir)
set<ODT_node>::iterator merge(set<ODT_node>::iterator it, bool dir) 表示把
flowchart LR
A(l1, r1, val) --> D[(merge it)]
C(l2, r2, val) --> D
D --> B(l1, r2, val)set<ODT_node>::iterator merge(set<ODT_node>::iterator it, bool dir) {
if (it == t.end()) return t.end();
// 如果 it 指向的是最后一个节点，则不需要合并
// 合并左边
if (dir) {
if (it == t.begin()) return t.end();
// 如果 it 指向的是第一个节点，则不需要合并
auto prev_it = prev(it);
// 左边的指针
if (prev_it->val == it->val) {
int l = prev_it->l, r = it->r, val = it->val;
// 预先记录信息
it = t.erase(prev_it);
if (it != t.end()) t.erase(it);
// 删除原节点
return t.insert({l, r, val}).first;
// 添加合并后的节点
}
return it;
}
// 合并右边（同上）
auto next_it = next(it);
if (next_it == t.end()) return t.end();
if (next_it->val == it->val) {
int l = it->l, r = next_it->r, val = it->val;
t.erase(it);
if (next_it != t.end()) t.erase(next_it);
return t.insert({l, r, val}).first;
}
return it;
}区间推平操作 —— void assign(int l, int r, int val)
void assign(int L, int R, int Val) 表示把
flowchart LR
a(l, r, val) --> D[(assign L, R, Val)]
b(……) --> D
c(l, r, val) --> D
g(l, r, val) --> D
e(……) --> D
f(l, r, val) --> D
D --> h(l, r, val)
D --> i(……)
D --> j(l, L - 1, val)
D --> k(L, R, Val)
D --> l(R + 1, r, val)
D --> m(……)
D --> n(l, r)具体过程为在
void assign(int l, int r, int val) {
auto ir = split(r + 1), il = split(l);
// 分裂操作端点（必须先分裂 r 再分裂 l 不然迭代器会失效）
t.erase(il, ir);
// 删除中间的一段被赋值的区间的原节点
t.insert({l, r, val});
// 重新插入被赋值的区间
it = merge(it, 1); merge(it, 0);
// 合并端点
}其他的区间修改操作 —— void fun(int l, int r, ……)
珂朵莉树修改操作都可以按一下模板操作（类比分块）。
在
void fun(int l, int r, ……) {
auto ir = split(r + 1), il = split(l);
// 分裂操作端点
for (auto it = il; it != ir; it ++ )
// 对中间的节点操作
merge(find(l), 1); merge(find(r), 0);
// 合并端点
}区间查询操作 —— int fun(int l, int r)
珂朵莉树查询操作都可以按一下模板操作（y 也类比分块）。
在
int fun(int l, int r) {
auto ir = split(r + 1), il = split(l);
// 分裂操作端点
for (auto it = il; it != ir; it ++ )
// 对中间的节点贡献
merge(find(l), 1); merge(find(r), 0);
// 合并端点
}total-code
struct ODT_node {
int l, r;
mutable int val;
bool operator < (const ODT_node x) const {return l < x.l;}
};
struct ODT {
set<ODT_node> t;
void build(int a[], int n) {
int x = a[1], pos = 1;
for (int i = 2; i <= n; i++) {
if (a[i] != x) {
t.insert({pos, i - 1, x});
pos = i; x = a[i];
}
}
t.insert({pos, n, a[n]});
}
set<ODT_node>::iterator find(int x) {
auto it = t.lower_bound({x, 0, 0});
if (it == t.end() || it->l > x) it--;
return it;
}
set<ODT_node>::iterator split(int x) {
auto it = find(x);
if (it->l == x) return it;
int l = it->l, r = it->r, val = it->val;
t.erase(it); t.insert({l, x - 1, val});
return t.insert({x, r, val}).first;
}
set<ODT_node>::iterator merge(set<ODT_node>::iterator it, bool dir) {
if (it == t.end()) return t.end();
if (dir) {
if (it == t.begin()) return t.end();
auto prev_it = prev(it);
if (prev_it->val == it->val) {
int l = prev_it->l, r = it->r, val = it->val;
it = t.erase(prev_it);
if (it != t.end()) t.erase(it);
return t.insert({l, r, val}).first;
}
return it;
}
auto next_it = next(it);
if (next_it == t.end()) return t.end();
if (next_it->val == it->val) {
int l = it->l, r = next_it->r, val = it->val;
t.erase(it);
if (next_it != t.end()) t.erase(next_it);
return t.insert({l, r, val}).first;
}
return it;
}
void assign(int l, int r, int val) {
auto ir = split(r + 1), il = split(l);
t.erase(il, ir);
auto it = t.insert({l, r, val}).first;
it = merge(it, 1); merge(it, 0);
}
void fun(int l, int r, ……) {
auto ir = split(r + 1), il = split(l);
for (auto it = il; it != ir; it ++ )
// 对中间的节点操作
merge(find(l), 1); merge(find(r), 0);
}
int fun(int l, int r) {
auto ir = split(r + 1), il = split(l);
for (auto it = il; it != ir; it ++ )
// 对中间的节点贡献
merge(find(l), 1); merge(find(r), 0);
}
};例题
上帝造题的七分钟 2 / 花神游历各国
Willem, Chtholly and Seniorious
序列