大家好，欢迎来到IT知识分享网。
关于它很珂学的名字…
珂朵莉树（Chtholly Tree），又称老司机树（Old Driver Tree），起源于CodeFoeces平台上编号为896C的一道题—— “ Willem, Chtholly and Seniorious ” （珂学家们此时不用翻译也知道这个名字是在说啥了） ，一位用户Old Driver在给出了线段树的正解之后，又发布了YY多年的 一份前所未有的玄学解法，其中利用到的数据结构就是今日我们喜闻乐见的 珂朵莉树。
它可以干什么
很简单，在具有区间赋值操作，区间统计操作，以及最好保证数据随机的情况下在时空复杂度上把线段树吊起来打（详情见后）。
也可以在走投无路时 骗分。
你需要有哪些前置知识…
- 五分钟就能学会的C++STL中set的部分内容
- 暴力枚举
- 数学知识（如果你想证明它的玄学复杂度的话）
- 没了
嗯…真正有用的不过是前两条而已。
各种声明以及初始化
珂朵莉树的节点
应该是你要写珂朵莉树时首先要做的…
typedef bool type;
struct Node
{
unsigned int l;
unsigned int r;
mutable type data;
Node(unsigned int a, unsigned int b = 0, type c = 0);
bool operator <(const Node &a) const
{
return l < a.l;
}
};
Node::Node(unsigned int a, unsigned int b, type c)
{
l = a;
r = b;
data = c;
}
解释一下上面的代码。
- 珂朵莉树的每一个节点代表着一个闭区间，那么Node结构体里理应有这个区间的左右边界（即l和r）。
- type和data是当前区间统一的类型与数值，就是说闭区间[l,r]内每个点的类型都是type（自己定义的，这里我使用了bool作为type，到底是什么无所谓），值都是data。（当然，我们只考虑离散的点）
- data需要mutable修饰，这样我们可以在set中利用迭代器修改它。
- 对于结构体，我们自然需要构造函数，无需多讲。
- 由于我们使用set来存储Node，所以我们需要重载小于号，使其按照左端点排序。
构造珂朵莉树
#include <set>
set<Node> s;
没错这就完事了
就这么简单，你得到了一个没有初始化的珂朵莉树。
一般来说，我们通过给定数据，向其中不断插入区间长度为1的区间来完成初始化。
比如形如这样的话：“第二行包括n个数，表示序列的初始状态”（摘自SCOI2010 序列操作）。
我们就可以这样初始化：
for (int i = 0; i < n; ++i)
{
static type temp = 0;
cin >> temp;
s.insert(Node(i, i, temp));
}
s.insert(Node(n, n, 0));
你的序列下标从0或者1开始是无所谓的。
这里有一个蜜汁细节，就是在把所有给定数据插入完成之后，需要在末尾多插入一个节点。我也不知道这究竟有啥用，根据自己测试貌似做不做这一步并没有什么区别，反正是玄学，信就完事了。
懒人宏定义
我个人并不是很懒，但是声明迭代器真的很令人痛苦。于是我选择了这样
#define S_IT set<Node>::iterator //S_IT = set_iterator
据我所知，这个宏定义是大部分写珂朵莉树的coder都选择了的。
你也可以自己搞一些更懒的宏定义。
至此，准备工作结束。
核心操作
分裂：split
既然我们要进行区间操作，那就得把这个区间拿出来（就是这么暴力的思想） 。
split(pos)操作将包含位置pos的区间[l,r]分裂成[l,pos-1]和[pos,r]，并返回后者的迭代器。
S_IT split(unsigned int pos)
{
S_IT it = s.lower_bound(Node(pos));
if (it != s.end() && it->l == pos)
return it;
--it;
unsigned int l = it->l, r = it->r;
type data = it->data;
s.erase(it);
s.insert(Node(l, pos - 1, data));
return s.insert(Node(pos, r, data)).first;
}
我们先利用lower_bound()函数在set中查到左端点位置大于等于pos的节点。
如果这个节点的左端点位置正是pos，那么我们无需分裂，直接返回。
如果它的左端点位置不是pos，那么必然大于pos，则包含位置pos的节点是上一个节点，it-=1。
接下来的事情就好办了，暴力分裂再插入即可。不要忘了返回值。
此时，如果我们想使用区间[l,r]中的数据，只需要这么写：
S_IT it2 = split(r + 1), it1 = split(l);
for (; it1 != it2; ++it1)
{
； //利用迭代器it1搞些事情
}
这里有一个细节必须注意，必须先声明it2再声明it1，否则根据split中的erase操作，迭代器it1可能会失效。（因为it1所属的节点可能被删除了）
区间赋值：assign
珂朵莉树最重要的操作，也是不让它退化为暴力算法的玄学 保障。
既然一个区间内所有的值全都一样了，那么在珂朵莉树中这个区间就可以只用一个节点来表示。这就是珂朵莉树的核心，光速降低节点数量的神器。
void assign(unsigned int l, unsigned int r, type val)
{
S_IT it2 = split(r + 1), it1 = split(l);
s.erase(it1, it2);
s.insert(Node(l, r, val));
return;
}
可见，这个区间里所有的节点全部被删除，使用一个新的节点来代替。
根据我并不会的 证明，assign的区间长度在随机数据下的期望为N/3，十分恐怖。
而且这个assign在赋值之余还可以顺便做做区间统计啥的，根据情况而定
至此，珂朵莉树的核心操作介绍完毕。
附加的工作？
很多时候，一道题不可能只用两个函数就轻松搞定，需要额外的暴力函数与算法，是的就是暴力。
由于暴力算法大家肯定会，又怕大家不好理解，所以在这里贴一下我写的的CF896C的代码。
这道题虽说是起源，但是还是比较有难度的，认为太难的可以直接往下走，看另一个例子。
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define S_IT set<Node>::iterator
typedef long long ll;
struct Node
{
int l, r;
mutable ll val;
bool operator <(const Node &a) const
{
return l < a.l;
}
Node(int a, int b, ll v);
Node(int a);
};
S_IT split(int pos);
void add(int l, int r, int v);
ll kth(int l, int r, int k);
ll qpow(ll a, int b, ll y);
ll query(int l, int r, int x, ll y);
void assign(int l, int r, int v);
int rnd(void);
set<Node> s;
ll seed;
int n, m, vmax;
int main(void)
{
ios::sync_with_stdio(false);
cin >> n >> m >> seed >> vmax;
for (int i = 1; i <= n; ++i)
{
static int temp = 0;
temp = rnd() % vmax + 1;
s.insert(Node(i, i, (ll)temp));
}
s.insert(Node(n + 1, n + 1, 0));
for (int i = 1; i <= m; ++i)
{
static int l = 0, r = 0, x = 0, y = 0, op = 0;
op = rnd() % 4 + 1;
l = rnd() % n + 1, r = rnd() % n + 1;
if (l > r)
{
swap(l, r);
}
if (op == 3)
{
x = rnd() % (r - l + 1) + 1;
}
else
{
x = rnd() % vmax + 1;
}
if (op == 4)
{
y = rnd() % vmax + 1;
}
if (op == 1)
{
add(l, r, (ll)x);
}
else if (op == 2)
{
assign(l, r, (ll)x);
}
else if (op == 3)
{
cout << kth(l, r, x) << endl;
}
else if (op == 4)
{
cout << query(l, r, x, (ll)y) << endl;
}
}
//system("pause");
return 0;
}
Node::Node(int a, int b, ll v)
{
l = a;
r = b;
val = v;
}
Node::Node(int a)
{
l = a;
}
S_IT split(int pos)
{
S_IT it = s.lower_bound(Node(pos));
if (it != s.end() && it->l == pos)
{
return it;
}
--it;
int l = it->l, r = it->r;
ll val = it->val;
s.erase(it);
s.insert(Node(l, pos - 1, val));
return s.insert(Node(pos, r, val)).first;
}
void add(int l, int r, int v)
{
S_IT it2 = split(r + 1), it1 = split(l);
for (S_IT it=it1; it != it2; ++it)
{
it->val += v;
}
}
ll kth(int l, int r, int k)
{
S_IT it2 = split(r + 1), it1 = split(l);
vector<pair<ll, int> >arr;
arr.clear();
for (S_IT it = it1; it != it2; ++it)
{
arr.push_back(pair<ll, int>(it->val, it->r - it->l + 1));
}
sort(arr.begin(), arr.end());
for (unsigned int i = 0; i < arr.size(); ++i)
{
k -= arr[i].second;
if (k <= 0)
{
return arr[i].first;
}
}
}
ll qpow(ll a, int x, ll y)
{
ll b = 1LL;
a %= y;
while (x)
{
if (x & 1)
{
b = (b*a) % y;
}
a = (a*a) % y;
x >>= 1;
}
return b;
}
ll query(int l, int r, int x, ll y)
{
S_IT it2 = split(r + 1), it1 = split(l);
ll res = 0;
for (S_IT it = it1; it != it2; ++it)
{
res = (res + (it->r - it->l + 1)*qpow(it->val, x, y)) % y;
}
return res;
}
void assign(int l, int r, int v)
{
S_IT it2 = split(r + 1), it1 = split(l);
s.erase(it1, it2);
s.insert(Node(l, r, v));
}
int rnd(void)
{
int ret = (int)seed;
seed = (seed * 7 + 13) % 1000000007;
return ret;
}
SCOI2010 序列操作也是可以用珂朵莉树暴力写出来的一道题，尽管数据不随机。
这道题相比之下简单一些额外的操作较少，各个函数也比较容易理解。
#include <iostream>
#include <set>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define S_IT set<Node>::iterator
#define MAXN 100002
typedef long long ll;
typedef bool type;
struct Node
{
unsigned int l;
unsigned int r;
mutable type data;
Node(unsigned int a, unsigned int b = 0, type c = 0);
bool operator <(const Node &a) const
{
return l < a.l;
}
};
S_IT split(unsigned int pos);
void assign(unsigned int l, unsigned int r, type val);
void rev(unsigned int l, unsigned int r);
int sum(unsigned int l, unsigned int r);
int count(unsigned int l, unsigned int r);
set<Node> s;
int main(void)
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
static type temp = 0;
cin >> temp;
s.insert(Node(i, i, temp));
}
s.insert(Node(n, n, 0));
while (m--)
{
static unsigned int op = 0, a = 0, b = 0;
cin >> op >> a >> b;
if (op == 0)
{
assign(a, b, 0);
}
else if (op == 1)
{
assign(a, b, 1);
}
else if (op == 2)
{
rev(a, b);
}
else if (op == 3)
{
cout << sum(a, b) << endl;
}
else
{
cout << count(a, b) << endl;
}
}
system("pause");
return 0;
}
Node::Node(unsigned int a, unsigned int b, type c)
{
l = a;
r = b;
data = c;
}
S_IT split(unsigned int pos)
{
S_IT it = s.lower_bound(Node(pos));
if (it != s.end() && it->l == pos)
return it;
--it;
unsigned int l = it->l, r = it->r;
type data = it->data;
s.erase(it);
s.insert(Node(l, pos - 1, data));
return s.insert(Node(pos, r, data)).first;
}
void assign(unsigned int l, unsigned int r, type val)
{
S_IT it2 = split(r + 1), it1 = split(l);
s.erase(it1, it2);
s.insert(Node(l, r, val));
return;
}
void rev(unsigned int l, unsigned int r)
{
S_IT it2 = split(r + 1), it1 = split(l);
for (; it1 != it2; ++it1)
{
it1->data ^= 1;
}
}
int sum(unsigned int l, unsigned int r)
{
S_IT it2 = split(r + 1), it1 = split(l);
int res = 0;
for (; it1 != it2; ++it1)
{
res += it1->data ? it1->r - it1->l + 1 : 0;
}
return res;
}
int count(unsigned int l, unsigned int r)
{
int res = 0, temp = 0;
S_IT it2 = split(r + 1), it1 = split(l);
for (; it1 != it2; ++it1)
{
if (it1->data)
{
temp += it1->r - it1->l + 1;
}
else
{
res = max(res, temp);
temp = 0;
}
}
return max(res, temp);
}
最后的话
根据数学（玄）分析，珂朵莉树的各种操作的总体复杂度始终为O(NlogN)，这会吊打某些常数大，附加工作会影响总体复杂度的线段树算法。
举个例子，洛谷P2787，有两种写法，线段树和珂朵莉树。
先看看一个哥们（我并不认识）的线段树代码（注意右上角的耗时与内存）
然后是我的珂朵莉树代码（我开了O2优化，不开的话用时增加0.5倍左右）。
线段树被吊打。
至此，你大致了解完了珂朵莉树的全部基本操作。
End.
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/25895.html
