珂朵莉树学习笔记
StudyingFather
2019-08-01 21:58:58
珂朵莉树（Chtholly Tree），又名老司机树（Old Driver Tree, ODT），是一种非常暴力的维护序列信息的数据结构。
其通过维护值相同的连续段来保证效率，在特殊构造的数据下会退化为普通暴力算法。
**注：下列代码均可以在 `C++14` 标准下编译。**
## 1 前置知识
1. 熟练掌握 `std::set` 的用法。
没了？没错。
## 2 一个例子
[CF896C](http://codeforces.com/problemset/problem/896/C) 是一个非常经典的模板题，珂朵莉树也正是来源于本题。
下面是题面部分：
> 你需要维护一个序列，并支持如下几种操作：
>
> 1. 给区间 $ [l,r] $ 内的所有数字加上 $ x $ 。
> 2. 将区间 $ [l,r] $ 内的所有数字赋值为 $ x $ 。
> 3. 求区间 $ [l,r] $ 内所有数字中第 $ x $ 小的数字（重复数字多次计算）。
> 4. 求 $ \sum_{i=l}^{r} a_i^x \bmod y $ 的值。
>
> 题目保证数据随机。
前三个操作都不算太难，使用常规的数据结构（主席树）都可以圆满解决。
问题在于第四个操作。为什么常规的数据结构在第四个操作面前无能为力呢？主要在于其并不能方便地分解为两个子区间的问题。
这时候珂朵莉树就要出场了。
## 3 ODT 的基本操作
### 3.1 节点结构
我们这样定义一个珂朵莉树的节点：
```cpp
struct node
{
int l,r;//该节点对应的区间
mutable long long val;
//mutable 修饰该变量之后，就可以直接在 set 中修改该变量的值，而不是取出元素修改后再重新插入 set
node(int L,int R=-1,long long Val=0)
{
l=L,r=R,val=Val;
}
bool operator<(const node&a)const
{
return l<a.l;
}
};
```
接下来，我们定义一个 `set<node> odt` 来维护一棵 ODT。
### 3.2 分割区间操作：split
给出一个区间 $ [l,r] $ 和一个位置 $ pos $ ，怎么把这个区间分割为 $ [l,pos-1] $ 和 $ [pos,r] $ 两个区间呢？
大致流程很简单：
1. 先在 ODT 中找到含有 $ pos $ 位置的区间。
2. 如果 $ pos $ 已经是一个区间的左端点，则无需分割。
3. 否则我们把原来的区间删除，插入两个新区间。
详细代码如下：
```cpp
auto split(int pos)
{
auto it=odt.lower_bound(node(pos));//找到左端点不小于 pos 的区间
if(it!=odt.end()&&it->l==pos)return it;//pos 是区间左端点时无需分割
it--;//pos 一定在前一个区间中
int l=it->l,r=it->r;
long long val=it->val;
odt.erase(it);//删除原来的区间
odt.insert(node(l,pos-1,val));
return odt.insert(node(pos,r,val)).first;//插入两个新区间
//这里的返回值是后半段区间对应的迭代器
}
```
经过这样的分割操作后，容易发现任意两个区间没有相交的部分，这是保证我们接下来操作正确性的前提。
### 3.3 合并区间操作：assign
如果光分割区间而不合并的话，我们事实上就是对一堆长度为 $ 1 $ 的区间进行操作，珂朵莉树也就会退化为普通暴力算法。
通过合并操作，我们可以迅速降低珂朵莉树的大小，保证珂朵莉树的效率。
这里先给出合并操作的代码：
```cpp
void assign(int l,int r,long long val)
{
auto itr=split(r+1),itl=split(l);
odt.erase(itl,itr);//删除[itl,itr)区间内的所有元素（注意左闭右开区间）
odt.insert(node(l,r,val));//将原来的诸多小区间用一个大区间代替
}
```
注意：**在执行 `split` 操作时，应先 `split` 右端点，再 `split` 左端点**，否则可能会 RE。
通过两次 `split` 操作， $ [l,r] $ 区间内一定都是整段区间。因此我们可以安全地删除原来的零散区间，用大区间代替。
经过 `assign` 操作后，ODT 的规模会下降不少，从而保证 ODT 的实际运行效率。
### 3.4 其他操作
所有区间操作都可以套这样的一个模板：
1. 先 `split` 右端点，再 `split` 左端点，获得两个端点（左闭右开）的迭代器。
2. 对两个端点之间的所有区间暴力更改。
代码差不多长这样：
```cpp
void update(int l,int r)
{
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
//do something
}
```
我们回到那道模板题。
首先是区间加一个值：
```cpp
void add(int l,int r,long long val)
{
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
it->val+=val;//因为 val 被 mutable 关键字修饰，从而可以直接修改 set 里元素的值
}
```
接下来是区间第 $ k $ 小，暴力取出区间内所有段排序一遍即可：
```cpp
typedef pair<long long,int> pii;
long long kth(int l,int r,int k)
{
vector<pii> a;
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
a.push_back(pii(it->val,(it->r)-(it->l)+1));
sort(a.begin(),a.end());
for(auto it=a.begin();it!=a.end();it++)
{
k-=it->second;
if(k<=0)return it->first;
}
return -1;
}
```
然后是区间幂次和，还是暴力，取出区间内所有段累加求和：
```cpp
long long sum(int l,int r,int x,int y)
{
long long ans=0;
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
ans=(ans+fpow(it->val,x,y)*((it->r)-(it->l)+1))%y;
return ans;
}
```
**注意到我们的区间操作都是直接对值相同的连续段进行处理，当段数较多的时候，效率就会降低。**
模板题的完整代码如下：
```cpp
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#define MOD 1000000007
using namespace std;
struct node
{
int l,r;
mutable long long val;
node(int L,int R=-1,long long Val=0)
{
l=L,r=R,val=Val;
}
bool operator<(const node&a)const
{
return l<a.l;
}
};
typedef pair<long long,int> pii;
set<node> odt;
long long a[100005],n,m,seed,vmax;
long long rnd()
{
long long ret=seed;
seed=(seed*7+13)%MOD;
return ret;
}
long long fpow(long long x,long long y,long long mod)
{
long long ans=1;
x%=mod;
while(y)
{
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
auto split(int pos)
{
auto it=odt.lower_bound(node(pos));
if(it!=odt.end()&&it->l==pos)return it;
it--;
int l=it->l,r=it->r;
long long val=it->val;
odt.erase(it);
odt.insert(node(l,pos-1,val));
return odt.insert(node(pos,r,val)).first;
}
void assign(int l,int r,long long val)
{
auto itr=split(r+1),itl=split(l);
odt.erase(itl,itr);
odt.insert(node(l,r,val));
}
void add(int l,int r,long long val)
{
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
it->val+=val;
}
long long kth(int l,int r,int k)
{
vector<pii> a;
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
a.push_back(pii(it->val,(it->r)-(it->l)+1));
sort(a.begin(),a.end());
for(auto it=a.begin();it!=a.end();it++)
{
k-=it->second;
if(k<=0)return it->first;
}
return -1;
}
long long sum(int l,int r,int x,int y)
{
long long ans=0;
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
ans=(ans+fpow(it->val,x,y)*((it->r)-(it->l)+1))%y;
return ans;
}
int main()
{
cin>>n>>m>>seed>>vmax;
for(int i=1;i<=n;i++)
{
a[i]=rnd()%vmax+1;
odt.insert(node(i,i,a[i]));
}
for(int i=1;i<=m;i++)
{
int op=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1,x,y;
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,x);
else if(op==2)assign(l,r,x);
else if(op==3)cout<<kth(l,r,x)<<endl;
else cout<<sum(l,r,x,y)<<endl;
}
return 0;
}
```
## 4 效率？
ODT 的做法看起来非常暴力，但是在随机数据的情况下，它的表现其实非常优秀。
我们可以证明，一个有 $n$ 个数的序列，在经过 $k$ 次**随机的**区间赋值操作后，期望段数大约在 $O(\dfrac{n}{k})$ 的级别。
证明可以点击 [这里](https://codeforces.com/blog/entry/56135?#comment-398940) 查看，这里不再展开。
在模板题中，因为数据随机，有 $\dfrac{1}{4}$ 的操作均为**随机的**区间赋值操作，因此 ODT 的实际段数很低，效率当然不错。
## 5 一点扩展
珂朵莉树并不单单只能解决序列问题，对于树上问题，可以通过重链剖分后转化为序列问题，再考虑用珂朵莉树解题。
当然珂朵莉树虽然名为树，也并不一定必须用平衡树（`std::set`）实现。
我们发现区间分裂操作就是删除一个区间，再插入两个小区间；区间合并操作就是将一些区间删掉，再插入一个更大的区间。这个操作可以使用链表来实现，效率也很不错。
## 6 总结
说了这么多，不过要注意的是：使用珂朵莉树的前提是题目有区间赋值的性质，且数据随机。
**在数据中区间赋值操作较多的时候，珂朵莉树的实际运行效率较高**。但特殊构造的数据往往并不具有这样的性质，导致其退化为普通暴力算法，因此要结合题目性质来考虑是否使用珂朵莉树来解题。
虽然事实上珂朵莉树在很多题目中都可以用其他常规数据结构代替，但其简单直接，易于调试的特点让它成为了一个解决不少题目的第二选择。