珂朵莉树学习笔记

· · 算法·理论

upd on 2026/9/15

修改了merge部分的表述，并添加了一道推荐题目。

我们的目标是：让所有人~观看末日三问~学会珂朵莉树。

算法介绍

珂朵莉树-老司机树-ODT。

ODT 是一种基于平衡树的暴力数据结构。它适用于有大量区间赋值、且查询可以暴力扫段的题目。

算法的核心在于，把一段同色的序列合并成一个结点，从而控制其他操作暴力枚举时的次数。

ODT 的复杂度是神秘的，依赖于数据。在随机数据跑得非常快，在构造数据非常容易被卡。

但是 ODT 非常好学和好写。本人学习并完成一道例题不超过两个小时。

算法实现

我假装不知道 CF896C 是 ODT 的模板题，我使用 P1558 作为例题来进行一个讲解。

题目告诉你，长度为 n 的序列，初始全为颜色 1，颜色范围 1 \sim m。

有两种操作：

这个题好！虽然正解是线段树，但是没有卡 ODT！

节点定义

struct Node{
    int l,r;
    mutable int v;
    bool operator<(const Node& other)const{
        return l<other.l;
    }
};
set<Node> odt;

表示 [l,r] 这个区间内的颜色都是 v，把它压成一个节点。

::::info[关于mutable int v] mutable 的意思是，这个成员变量即使在 const 函数里，也允许被修改。

加上这个东西，使可以通过 set 迭代器修改 v。

初始化

odt.insert(Node{1,n,1});

加入一个节点，用于表示，范围为 [l,r] 且颜色为 1 的区间。

split

ODT 最重要的操作。

set<Node>::iterator split(int x){
    if(x>n) return odt.end();

    // 找到第一个 l >= x 的区间
    set<Node>::iterator t=odt.lower_bound(Node{x,0,0});

    // 如果 x 正好是某个区间的左端点，不用切
    if(t!=odt.end()&&x==t->l) return t;

    // 否则 t 去前一个，就是包含 x 的那个区间
    t--;
    int L=t->l,R=t->r,V=t->v;

    // 删掉原区间，拆成 [L, x-1] 和 [x, R]
    odt.erase(t);
    odt.insert(Node{L,x-1,V});
    return odt.insert(Node{x,R,V}).fir;
}

把包含 x 的区间从 x 处切开，搞出两个新区间，方便后续操作。

assign

ODT 另一个最重要的操作。

void assign(int l,int r,int v){
    set<Node>::iterator R=split(r+1);
    set<Node>::iterator L=split(l);
    odt.erase(L,R);
    set<Node>::iterator t=odt.insert(Node{l,r,v}).fir;
}

这个应该看得懂，就是把 l 和 r 所在的区间切开，然后把本来 [l,r] 之间的区间全都合并成一个区间。

唯一要注意的点是先 split 右边界。

::::info[为什么先切右边] split 会进行 erase 和 insert，可能让已有迭代器失效。

::::

assign 操作可以在一定程度上保证 ODT 的复杂度。

merge

split 会把一个区间切成两段，切出来的两段颜色相同。

如果之后 assign 又把它染成和相邻段一样的颜色，就会留下相邻同色的段。

这导致 ODT 的时间复杂度退化。

所以我们需要 merge！

set<Node>::iterator merge(set<Node>::iterator t){
    set<Node>::iterator nxt=t;
    nxt++;
    if(nxt!=odt.end()&&nxt->v==t->v){
        int L=t->l,R=nxt->r,V=t->v;
        odt.erase(t);
        odt.erase(nxt);
        t=odt.insert(Node{L,R,V}).fir;
    }
    set<Node>::iterator pre=t;
    pre--;
    if(t!=odt.begin()&&pre->v==t->v){
        int L=pre->l,R=t->r,V=t->v;
        odt.erase(pre);
        odt.erase(t);
        t=odt.insert(Node{L,R,V}).fir;
    }
    return t;
}

这段代码意思是，如果当前节点的颜色和下一个相同，就和下一个合并；前一个相同，就和前一个合并。

在 assgin 的最后调用 merge(t) 即可。

query

int query(int l,int r){
    set<Node>::iterator R=split(r+1);
    set<Node>::iterator L=split(l);
    unordered_set<int> vis;
    for(auto i=L;i!=R;i++){
        vis.insert(i->v);
        if((int)vis.size()==m) return m;
    }
    return vis.size();
}

简单的，用 unordered_set 统计区间内颜色种类数。

针对本题的 hack，要加上 if((int)vis.size()==m) return m; 防止过量枚举。

其他操作

是暴力。

习题