珂朵莉树

珂朵莉树，ODT（Old Driver Tree），颜色段均摊都是它。其实我觉得硬说这是一种数据结构（尤其是“树”）是不恰当的，这更多应该是一种技巧。
与线段树等传统数据结构的区别在于：它可以更方便地维护每个被覆盖区间的值，因为我们认为对于一整个颜色段进行操作是容易的。如模板题中的操作 4：求 ∑i=lraix mod y\sum_{i=l}^ra_i^x\bmod y。

实现

一般用 std::set 实现。

节点

1
2
3
4
5
6
7
8
struct node{
    int l,r;
    mutable int val;
    bool operator<(const node &x)const{
        return l<x.l;
    }
};
set<node> odt;

ll 和 rr 表示这一段的区间，valval 表示这一段的权值，使用 mutable 修饰是为了使得结构体或函数在被 const 修饰后仍能修改 valval 的值，这样，我们就可以直接修改在 set 内部的元素的 valval。

split

用于将一个区间为 [l,r][l,r] 的区间分裂为 [l,pos)[l,pos) 和 [pos,r][pos,r]，并返回指向后者的迭代器的函数。

1
2
3
4
5
6
7
8
9
10
auto split(int pos){
    if(pos>n) return odt.end();
    auto it=odt.lower_bound({pos});
    if(it!=odt.end()&&it->l==pos) return it;//pos已是左端点，无需分割
    it--;//从上一个分割
    int l=it->l,r=it->r,val=it->val;
    odt.erase(it);//删除原区间
    odt.insert({l,pos-1,val});//左区间
    return odt.insert({pos,r,val}).first;//右区间
}

std::set.insert() 返回一个 std::pair<iterator,bool>，表示插入元素的迭代器及插入是否成功。
现代编译器应当都可以将 auto 识别为 std::set<node>::iterator。

assign

用于区间赋值。同时也是时间复杂度的保证，以模板题为例，大约 14\dfrac{1}{4} 的操作调用了 assign，而这个操作可以大幅减小 set 的大小。
特别注意：在截取 [l,r][l,r] 时一定要先调用 split(r+1) 再调用 split(l)，否则可能导致 RE。 具体原因可以看这里。我大致解释一下，就是若删除了迭代器 it，就会导致 it 及以后的迭代器失效，此时若强行访问失效部分就是 UB。如果我们先操作前面再操作后面，itl 和 itr 之间包含的区间就可能不是我们想要的那一部分。由此我们就需要特别注意，**珂朵莉树的任何涉及 erase 的操作都要先操作后面再操作前面。**如区间 swap。

1
2
3
4
5
6
void assign(int l,int r,int val){
    auto itr=split(r+1),itl=split(l);//截取[l,r]
    odt.erase(itl,itr);//删除[l,r]
    odt.insert({l,r,val});//插入新值
    return;
}

模板题

对于 1 操作，3 操作和 4 操作，直接分离出对应区间后暴力求解。2 操作直接用 assign。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node{
    int l,r;
    mutable ll val;
    bool operator<(const node &x)const{return l<x.l;}
};
ll qpow(ll a,int b,int mod){
    ll res=1;
    a%=mod;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
set<node> odt;
auto split(int pos){
    auto it=odt.lower_bound({pos});
    if(it!=odt.end()&&it->l==pos) return it;
    it--;
    int l=it->l,r=it->r;
    ll val=it->val;
    odt.erase(it);
    odt.insert({l,pos-1,val});
    return odt.insert({pos,r,val}).first;
}
void assign(int l,int r,int val){
    auto itr=split(r+1),itl=split(l);
    odt.erase(itl,itr);
    odt.insert({l,r,val});
    return;
}
void add(int l,int r,int val){
    auto itr=split(r+1),itl=split(l);
    for(;itl!=itr;itl++) itl->val+=val;
    return;
}
ll kth(int l,int r,int k){
    auto itr=split(r+1),itl=split(l);
    vector<pair<ll,int>> b;
    for(;itl!=itr;itl++)
        b.push_back({itl->val,itl->r-itl->l+1});
    sort(b.begin(),b.end());
    for(auto t:b){
        k-=t.second;
        if(k<=0) return t.first;
    }
    return 1145141919810LL;
}
ll sum(int l,int r,int x,int mod){
    ll res=0;
    auto itr=split(r+1),itl=split(l);
    for(;itl!=itr;itl++)
        res=(res+(qpow(itl->val,x,mod)*(itl->r-itl->l+1))%mod)%mod;
    return res;
}
const int N=1e5+10;
int n,m,seed,vmax,a[N],op,x,y,l,r;
int rnd(){
    int ret=seed;
    seed=(seed*7ll+13)%1000000007;
    return ret;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>seed>>vmax;
    for(int i=1;i<=n;i++){
        a[i]=(rnd()%vmax)+1;
        odt.insert({i,i,a[i]});
    }
    for(int i=1;i<=m;i++){
        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,x);
        else if(op==2) assign(l,r,x);
        else if(op==3) cout<<kth(l,r,x)<<'\n';
        else cout<<sum(l,r,x,y)<<'\n';
    }
    return 0;
}

习题

复杂度相关

我们可以从模板题中发现，这玩意除区间赋值外都需要暴力，所以是一种暴力数据结构。对于模板题，均摊时间复杂度 O(mlog⁡log⁡n)O(m\log\log n)（关于这个题的复杂度说法很多，具体是不是这个我也不是很清楚，原题严谨的复杂度分析极其复杂，这里不展开分析）。其时间复杂度保证完全依赖于 assign 操作，所以仅适用于：

  1. 数据随机生成的题，如序列；
  2. 区间查询后立即在查询区间 assign 的，这样通过势能分析可得复杂度为单 log⁡\log，如数列分块入门 8；
  3. 其他可以通过复杂度分析证明复杂度正确的。

参考资料

https://oi-wiki.org/misc/odt/

OI
#数据结构
珂朵莉树
https://headless-piston.github.io/2025/05/22/珂朵莉树/
作者
headless-piston
发布于
2025年5月22日
许可协议