某科学的珂朵莉树

珂朵莉树概述

见 百度百科&bilibili 。

珂朵莉树又称老司机树（Chtholly Tree / Old Driver Tree）暴力数据结构，特别适用于处理区间赋值、区间修改等操作。该结构在随机数据下表现优异，尤其在处理大量区间操作时具有显著优势。

该数据结构最早在 Codeforces Round #394 (Div. 1) 的 C 题 CF-896C 中被提出，并因其题面中角色“珂朵莉”的名字而得名。在实际应用中，珂朵莉树常用于替代线段树或树状数组，在某些特定场景下实现更简洁、高效的代码逻辑。

前置知识

STL-set

简介

set 是 C++ STL 提供的标准关联容器，其核心特性包括元素唯一性和自动排序。底层基于红黑树（自平衡二叉搜索树）实现，这使得插入、删除和查找操作的时间复杂度均为 \(\Theta(\log n)\) ，能高效处理大规模数据。

迭代器 —— set::iterator

set 的迭代器是 const_iterator，不允许通过迭代器修改元素值（排除使用 mutable）。通过 begin() 和 end() 可获取正向迭代器（指向首元素和尾后位置），rbegin() 和 rend() 获取反向迭代器（指向尾元素和首前位置）。迭代器在插入/删除操作后不会失效（红黑树仅调整指针，不移动内存）。 迭代器使用方式与普通指针相同。迭代器支持两种操作为 const_iterator++、const_iterator--，分别指向前驱和后继。

查找 —— find()

find(value) 函数用于查找元素 value，返回指向该元素的迭代器；若不存在，返回 end()。时间复杂度为 \(\Theta(\log n)\)。
示例：

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 提供三种删除方式：

1. 按值删除：erase(value)，删除所有值为 value 的元素（set 中最多一个），返回删除的元素个数（0 或 1）。
2. 按迭代器删除：erase(it)，删除迭代器 it 指向的元素，无返回值。
3. 区间删除：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()。时间复杂度为 \(\Theta(\log n)\)，常用于二分查找或区间划分。
示例：

set<int> s = {1, 4, 6, 9}; 
auto it = s.lower_bound(5);  // 第一个 >=5 的元素是 6，it 指向 6 
cout << *it;  // 输出 6 

正文

节点存储信息 —— 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 需要重载运算符并按左端点排序
};

节点分裂操作 —— set<ODT_node>::iterator split(int x)

set<ODT_node>::iterator split(int x) 表示把一个包含 \(x\) 的节点按 \(x\) 分裂成两个节点并返回分裂后靠右节点的指针,如下：

flowchart LRA(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.lower_bound({x, 0, 0});// 找出要分裂的节点的下一个节点if (it != t.end() && it->l == x)	return it;// 若找不到要分裂的节点返回尾指针，防止越界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;// 删除要分裂的节点，插入分裂后的两个节点}

区间合并操作 —— void merge(set<ODT_node>::iterator it, bool dir)

void merge(set<ODT_node>::iterator it, bool dir) 表示把一 \(it\) 左右两边的与它相同的区间合并，\(dir = 1\) 合并左边，反之，如图：

flowchart LRA(l1, r1, val) --> D[(merge it)]C(l2, r2, val) --> DD --> B(l1, r2, val)

void merge(set<ODT_node>::iterator it, bool dir) {// 合并左边if (it != t.begin() && dir)  {auto prev_it = prev(it);// 左边的指针if (prev_it->val == it->val) {int l = prev_it->l, r = it->r, val = it->val;// 预先记录信息t.erase(prev_it);   t.erase(it); // 删除原节点it = t.insert({l,  r, val}).first;// 添加合并后的节点}}// 合并右边（同上）if (!dir) {auto next_it = next(it);if (next_it != t.end()  && next_it->val == it->val) {int l = it->l, r = next_it->r, val = it->val;t.erase(next_it);   t.erase(it);t.insert({l,  r, val});}}
}

区间推平操作 —— void assign(int l, int r, int val)

void assign(int L, int R, int Val) 表示把 \(L\) 到 \(R\) 区间内的数赋值为 \(Val\)，如下：

flowchart LRa(l, r, val) --> D[(assign L, R, Val)]b(……) --> Dc(l, r, val) --> Dg(l, r, val) --> De(……) --> Df(l, r, val) --> DD --> 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)

具体过程为在 \(L\) 和 \(R + 1\) 处分裂，删除中间的一段被赋值的区间的原节点，最后重新插入被赋值的区间。

void assign(int l, int r, int val) {auto ir = split(r + 1), il = split(l);// 分裂操作端点t.erase(il, ir);// 删除中间的一段被赋值的区间的原节点t.insert({l, r, val});// 重新插入被赋值的区间merge(it, 1);	merge(it, 0);// 合并端点
}

其他的区间修改操作 —— void fun(int l, int r, ……)

珂朵莉树修改操作都可以按一下模板操作（类比分块）。

在 \(L\) 和 \(R + 1\) 处分裂，修改中间的一段被操作的区间的节点。

void fun(int l, int r, ……) {auto ir = split(r + 1), il = split(l);// 分裂操作端点for (auto it = il; it != ir; it ++ )// 对中间的节点操作merge(ir, 1);	merge(il, 0);// 合并端点
}

区间查询操作 —— int fun(int l, int r)

珂朵莉树查询操作都可以按一下模板操作（y也类比分块）。

在 \(L\) 和 \(R + 1\) 处分裂，计算中间的一段被查询的区间的贡献。

void fun(int l, int r) {auto ir = split(r + 1), il = split(l);// 分裂操作端点for (auto it = il; it != ir; it ++ )// 对中间的节点贡献merge(ir, 1);	merge(il, 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 l, int r, int val) {t.insert({l,  r, val});}set<ODT_node>::iterator split(int x) {auto it = t.lower_bound({x,  0, 0});if (it != t.end()  && it->l == x) return it;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;}void merge(set<ODT_node>::iterator it, bool dir) {if (it != t.begin() && dir)  {auto prev_it = prev(it);if (prev_it->val == it->val) {int l = prev_it->l, r = it->r, val = it->val;t.erase(prev_it); t.erase(it); it = t.insert({l,  r, val}).first;}}if (!dir) {auto next_it = next(it);if (next_it != t.end()  && next_it->val == it->val) {int l = it->l, r = next_it->r, val = it->val;t.erase(next_it); t.erase(it);t.insert({l,  r, val});}}}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;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(ir, 1);	merge(il, 0);}void fun(int l, int r) {auto ir = split(r + 1), il = split(l);for (auto it = il; it != ir; it ++ )// 对中间的节点贡献merge(ir, 1);	merge(il, 0);}
}