浅谈珂朵莉树

标签：浅谈 int text pos 朵莉树 split 端点

珂朵莉最可爱了。

好了不废话了，直接开始珂朵莉树。

什么是珂朵莉树

珂朵莉树，又叫老司机树，英文名字 \(\text{ODT}\)，是一种支持区间平推的乱搞数据结构，在数据随机时表现十分优秀。

操作

定义

珂朵莉树有链表和集合（\(\text{set}\)）两种定义方法，一般来说，使用 \(\text{set}\) 定义的比较普遍。

珂朵莉树的思想主要是将所有颜色相同（也就是数值相同）的区间缩成一个一个的块，将这些块的左右端点插入 \(\text{set}\) ，再进行后续操作。

举个小栗子，比如我现在有数列 \(a = \{ 1, 1, 2, 2, 1, 1, 1, 3\}\)，那么珂朵莉树里就应该存的是这样的信息：

\(s = \{\{1, 2, 1\}, \{3, 4, 2\}, \{5, 7, 1\}, \{8, 8, 3\}\}\)

解释一下第一个块表示的信息：左端点是 \(1\)，右端点是 \(2\)（即在区间 \([1, 2]\) 中），里面的数都是 \(1\)。

据证明，珂朵莉树在两个条件以下两个条件下复杂度优秀：

数据随机
操作中有平推操作

如果满足上面两个条件，珂朵莉树的复杂度就可以做到优秀的 \(O(n \log \log n) -O(n\log n)\) 了。

这样，我们就只需要在 \(\text{set}\) 中放入每个块的左右端点以及权值，并且按照左端点排序即可。

struct node {
    int l, r;
    mutable int v; // 注意这里的 mutable 一定不能改
    node(int L, int R = -1, int V = 0):l(L), r(R), v(V){}
    bool operator < (const node& W)const { // 按左端点排序
	return l < W.l;
    }
};
set<node> s;
#define itset set<node> :: iterator // 宏定义迭代器

建树

建树没啥好说的，就是把初始所有的点一个一个插进去。

for (int i = 1; i <= n; i ++ )
    s.insert(node(i, i, w[i]));

分裂（split）

\(\text{split(pos)}\) 操作是将 \(\text{pos}\) 所在的块分成两个，并返回右边块所在的迭代器。

当然，我们只需要在 \(\text{set}\) 中找到 \(\text{pos}\) 所在的迭代器，找到这个块的左端点 \(l\) 和右端点 \(r\)，删除原块，并加入 \([l, pos), [pos, r]\) 两块即可。

itset split(int pos) {
    itset p = s.lower_bound(node(pos)); // 找到左端点大于等于 pos 的第一个块
    // 当然也就是找到 pos 所在块右边的第一个块
    if (p != s.end() && p -> l == pos) return p;
    -- p; // pos 所在块就是 p
    int ls = p -> l, rs = p -> r, vv = p -> v;
    s.erase(p);
    s.insert(node(ls, pos - 1, vv));
    return s.insert(node(pos, rs, vv)).first;
}

平推（assign）

\(\text{assign(l, r, v)}\) 操作是将 \([l, r]\) 区间内都替换成 \(v\)。

当然，我们只要将 \(l, r\) 分裂出来，将 \([l, r + 1)\) 之间的删掉，最后插入块 \((l, r, v)\) 即可。

void assign(int l, int r, int v) {
    itset rs = split(r + 1), ls = split(l); // 注意这里 l, r 也不能反，r 别忘了加一（因为右端是开区间）
    s.erase(ls, rs);
    s.insert(node(l, r, v));
}

其他操作

操作思路和平推基本一样，就是取出 \([l, r]\) 之间的所有块，然后再一个一个处理即可。专家已经证明了，数据随机且平推的情况下，块数均摊不超过 \(\log n\)，所以就可以这样暴力乱搞了。

比如求 \([l, r]\) 之间的所有数的和：

int query(int l, int r) {
    itset rs = split(r + 1), ls = split(l);
    int ans = 0;
    for (itset it = ls; it != rs; it ++ )
    	ans += (it -> r - it -> l + 1) * it -> v;
    return ans;
}

好了，现在你已经完全掌握珂朵莉树了，拿几道小题练练手吧！