浅谈珂朵莉树

tkm2013 · 2026-10-23 09:11:50 · 算法·理论

本文同步发表于我的博客：

My blog

珂朵莉树，又称老司机树 ODT（Old Driver Tree），核心思想是把值相同的连续区间合并成一个节点，以此减少操作时需要遍历的节点数量。它在颜色段均摊和随机数据下表现非常出色。

节点

每个节点记录对应区间的左右端点，以及这个区间统一的颜色。

struct no{
    int l,r;
    mutable int c;//颜色
    no(int L,int R=-1,int C=0){l=L,r=R,c=C;}
    bool operator <(const no &x)const{return l<x.l;}
};

::::info[关于 mutable] mutable 与 const 相反，表示成员永远可修改。它使得在 set 中拿到迭代器后，可以直接修改节点内部的 c，而不需要取出节点再重新插入。 ::::

分裂

split 是珂朵莉树的核心操作之一：把包含位置 x 的区间从 x 处切开，返回以 x 为左端点的区间的迭代器。做法是用 lower_bound 找到第一个左端点不小于 x 的区间，如果它左端点恰好是 x 就直接返回；否则回退一个位置，取出包含 x 的原区间，删掉后重新插入 [l,x-1] 和 [x,r] 两个节点。

auto split(int x){
    if(x>n)return odt.end();//超过维护范围，返回哨兵
    auto it=odt.lower_bound(no(x));
    if(it!=odt.end() && it->l==x)return it;//左端点已经是x，无需分裂
    it--;int l=it->l,r=it->r,c=it->c;
    odt.erase(it);
    odt.insert(no{l,x-1,c});//左半段
    return odt.insert(no{x,r,c}).first;//返回右半段，insert有返回值
}

合并（区间赋值）

assign 用来把区间 [l,r] 推平成同一种颜色，这是珂朵莉树唯一能降低节点数量的操作，也是它在随机数据下高效的关键。

void assign(int l,int r,int c){
    auto itr=split(r+1),itl=split(l);
    odt.erase(itl,itr);
    odt.insert(no{l,r,c});
}

这里有几个容易踩的细节。第一，必须先 split(r+1)，再 split(l)。如果先分裂 l，可能改变包含 r+1 的节点，导致先前得到的迭代器失效，引发 RE。第二，erase 是左闭右开区间，所以右端点要分裂 r+1，删除范围才会真正覆盖到 r。

查询

查询类操作同样先分裂出区间边界，然后在中间暴力遍历节点。

int query(int l,int r){
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++){
        // 处理当前节点对答案的贡献
    }
    return ans;
}

不需要把区间合并回去。一次查询最多让节点数增加两个，如果每次都合并，反而会引入额外的删除与插入开销，得不偿失。

时间复杂度

珂朵莉树看起来非常暴力，但因为有区间赋值带来的均摊效果，在随机数据下可以通过大量题目。它的复杂度不是数据结构本身保证的，而是随机数据 + 足够多的 assign 换来的期望复杂度。

证明

设第 i 次操作遍历了 d_i 个节点，删除了 f_i 个节点，显然 f_i \le d_i。把当前节点总数看作势能。

初始有 O(n) 个节点。每次区间加或查询最多让节点数增加常数个，所以 m 次操作过程中曾经存在过的节点总数是 O(n+m)。删除的节点数不可能超过存在过的节点总数，因此

在随机数据下，assign 以常数概率出现，而一次操作遍历的节点数与删除的节点数同阶，所以总遍历量的期望为

再加上 set 每次查找前驱的 O(\log n)，总复杂度为

如果数据几乎不出现 assign，节点数只增不减，每次操作可能遍历 \Theta(n) 个节点，复杂度退化为 O(nm)，直接超时。所以写 ODT 之前必须确认：题目有区间赋值，且数据随机或近似随机。 考试中需要谨慎使用。

推荐题目