珂朵莉树（ODT）学习笔记

发表于 更新于 分类于 阅读次数： 本文字数： 11k
珂朵莉树，又名Old Driver Tree，能够解决对于一个序列进行推平（赋值）操作和遍历区间的问题，是一个暴力数据结构，对于随机的数据表现比较好。

珂朵莉树（ODT）

珂朵莉树，又名Old Driver Tree，能够解决对于一个序列进行推平（赋值）操作和遍历区间的问题，是一个暴力数据结构，对于随机的数据表现比较好。

原理是，对一个区间赋值后，这个区间每个元素的值应该都相同，这时我们如果把这段区间看成一个整体的话，进行若干次操作后整个数组被分成了若干个整体，所以我们定义一个结构体用来表示相同的段，这样，一个节点就能记录下一个区间的信息，我们只需要记录左右端点和值即可。并且，我们甚至只需要记录左端点即可，右端点通过下一个区间的左端点来判断。

实现

set实现

节点类型

我们定义节点类型是左右端点和区间的值，那么应该有：

1
2
3
4
5
6
7
8
struct Node{
  int l, r;
  mutable int v;
  Node(const int &l, const int &r, const int &v) : l(l), r(r), v(v) {}
  bool operator<(const Node &o) const {
    	return l < o.l;
  }
}

其中mutable代表可变的，让我们可以在后面的操作中修改\(v\)的值，而不受const影响。

节点存储

我们维护闭区间\([l,r]\)的信息，在未插入元素前，我们放置一个\([l, r+1]\)的节点，在之后插入节点后，我们把区间断开维护，每个set里面的元素都是闭区间

split操作

split操作是珂朵莉树的核心。它接受一个位置\(x\)，将原本包含点\(x\)的区间(\([l, r]\))，分裂成两个区间\([l,x)\)和\([x,r]\)，并返回指向后者的迭代器。

1
2
3
4
5
6
7
8
9
10
11
auto split(int x){
  auto it = odt.lower_bound({x, 0, 0});
  if(it != odt.end() && it->l == x){
    return it;
  }
  it--;
  int l = it->l, r = it->r, v = it->v;
  odt.erase(it);
  odt.insert({l, x-1, v});
  return odt.insert({x, r, v});
}

assign操作

ODT还有一个重要的操作：区间赋值，将所给区间\([l, r]\)赋值为\(v\)，首先，我们需要将区间\([l, r]\)截取出来，依次调用split(r+1),split(l)，（注意一定要按顺序，否则会影响迭代器返回的位置）将此两者返回的迭代器记作\(itr, irl\)，那么，区间\([itl, itr)\)就包含了我们需要赋值的区间。

之后，删除原有的信息，set的erase()方法可以传入两个迭代器，就删除了两个迭代器范围内的所有区间（左闭右开），最后插入新值。

1
2
3
4
5
void assign(int l, int r, int v){
  auto itr = split(r + 1), itl = split(l);
  odt.erase(itl, itr);
  odt.insert({l, r, v});
}

perform操作

perform操作指我们提取出一段区间并进行遍历，但是这样的操作不应该滥用，否则会破坏复杂度。我们的实现跟assign操作差不多，但是把删除区间改为遍历区间。

1
2
3
4
5
6
void perform(int l, int r){
  auto itr = split(r + 1), itl = split(l);
  for(;itl != itr;itl++){
    ...
  }
}

map实现

set实现中，我们发现区间右端点\(r\)其实是多余的，我们可以直接使用map记录下左端点对应的值。

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
struct ODT{
  const int n;
  map<int, int>mp;
  ODT(int n) : n(n) {mp[-1] = 0;}
  void split(int x){
    auto it = prev(mp.upper_bound(x));
    mp[x] = it->second;
  }
  void assign(int l, int r, int v){
    split(l);
    split(r + 1);//注意这里和下面都是r + 1
    auto it = mp.find(l);
    while(it->first != r + 1){
      it = mp.erase(it);
    }
    mp[l] = v;
  }
  void update(int l, int r, int c){
    split(l);
    split(r + 1);
    auto it = mp.find(l);
    while(it->first != r + 1){
      ...
      it = next(it);
    }
  }
};

复杂度分析

perform 以后立即对同一区间调用 assign

此时观察发现，两次 split 操作至多增加两个区间；一次 assign 将删除范围内的所有区间并增加一个区间，同时遍历所删除的区间。所以，我们所遍历的区间与所删除的区间数量成线性，而每次操作都只会增加\(O(1)\)个区间，所以我们操作的区间数量关于操作次数（包括初始化）成线性，时间复杂度为均摊\(O(m\log n)\)，其中\(m\)为操作次数，\(n\)为珂朵莉树中最大区间个数（可以认为\(n\le m\))。

perform 以后不进行 assign

如果允许特殊构造数据，这样一定是能被卡掉的，只需要使珂朵莉树中有足够多的不同区间并反复遍历，就能使珂朵莉树的复杂度达到甚至高于平方级别。

如果要保证复杂度正确，必须保证数据随机。详见 Codeforces 上关于珂朵莉树的复杂度的证明。更详细的严格证明见 珂朵莉树的复杂度分析。证明的结论是：用 std::set 实现的珂朵莉树的复杂度为\(O(m\log \log n)\)。

例题

Codeforces Round 449 Div.1 C

利用随机函数生成一个长度为\(n\)的序列，进行\(m\)次操作，每次操作为以下四种的一种：将给定区间内每个数都\(+x\)，将给定区间赋值为\(x\)，查询给定区间第\(x\)大的数，查询给定区间每个数的\(x\)次方之和。

题解

珂朵莉数的起源题。操作2是上面的split操作，操作1，3，4是上面的perform操作，对于操作3，求区间的第\(k\)大，我们可以暴力一些，但是直接把所有数都加入数组再排序还是会TLE，我们需要利用区间的数相同的性质，一个优化的方法是统计每个数的个数，以二元组的形式加入区间，排序后从左到右遍历，只要\(x\)小于当前数的个数，那么答案就是他了，否则\(x\)减去当前数的个数，继续寻找下一个数。

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
#define int long long

int rnd(int &seed) {
    int ret = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}

int qpow(int a, int b, int mod) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve() {
    int n;
    cin >> n;
    int m;
    cin >> m;
    int seed, vm;
    cin >> seed >> vm;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = rnd(seed) % vm + 1;
    }
    map<int, int> mp;
    mp[-1] = 0;
    for (int i = 0; i < n; i++) {
        mp[i] = a[i];
    }
    while (m--) {
        int x, y;
        int op = (rnd(seed) % 4) + 1;
        int l = (rnd(seed) % n) + 1;
        int r = (rnd(seed) % n) + 1;
        if (l > r) {
            swap(l, r);
        }
        if (op == 3) {
            x = (rnd(seed) % (r - l + 1));
        } else {
            x = (rnd(seed) % vm) + 1;
        }
        if (op == 4) {
            y = (rnd(seed) % vm) + 1;
        }
        l--;
        auto split = [&](int x) -> void {
            auto it = prev(mp.upper_bound(x));
            mp[x] = it->second;
        };
        if (op == 1) {
            split(l);
            split(r);
            auto it = mp.find(l);
            while (it->first != r) {
                it->second += x;
                it = next(it);
            }
        } else if (op == 2) {
            split(l);
            split(r);
            auto it = mp.find(l);
            while (it->first != r) {
                it = mp.erase(it);
            }
            mp[l] = x;
        } else if (op == 3) {
            vector<array<int, 2>> check;
            split(l);
            split(r);
            auto it = mp.find(l);
            while (it->first != r) {
                check.push_back({it->second, next(it)->first - it->first});
                it = next(it);
            }
            sort(check.begin(), check.end());
            for (auto [a, b] : check) {
                if (x < b) {
                    cout << a << "\n";
                    break;
                }
                x -= b;
            }
        } else {
            split(l);
            split(r);
            auto it = mp.find(l);
            int ans = 0;
            while (it->first != r) {
                ans = (ans + (next(it)->first - it->first) *
                                 qpow(it->second % y, x, y) % y) %
                      y;
                it = next(it);
            }
            cout << ans << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Educational Codeforces Round 36(Rated for Div.2) E

给定一段长度为\(n\)连续的日期，初始都赋值为1，给定\(q\)次操作，每次指定一个区间，把这段区间全部变成0或者全部变成1，每次操作后给出区间内1的个数。

题解

同样是珂朵莉树的模版，由于不断在合并区间，所以跑的还是很快的（1e9的\(n\)，珂朵莉树不过线段树也难过）。

对于赋值为1的操作，需要把原来就是1的区间先从答案中减掉，最后再一起赋值并更新答案；而对于赋值为0的操作，就扫描的时候把值已经是1的区间减掉即可，最后统一赋值为0。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, q;
    cin >> n >> q;
    map<int, int> f;
    f[0] = 1;
    auto split = [&](int x) -> void {
        auto it = prev(f.upper_bound(x));
        f[x] = it->second;
    };
    int ans = n;
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        l--;
        split(l);
        split(r);
        if (k == 1) {
            auto it = f.find(l);
            while (it->first != r) {
                ans -= it->second * (next(it)->first - it->first);
                it = f.erase(it);
            }
            f[l] = 0;
        } else {
            auto it = f.find(l);
            while (it->first != r) {
                ans -= it->second * (next(it)->first - it->first);
                it = f.erase(it);
            }
            f[l] = 1;
            ans += r - l;
        }
        cout << ans << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Codeforces Round 771 Div.2 E

给定一个有颜色的序列，初始所有颜色都是1，每个元素都有一个值，初始都是0，可以进行如下操作：1. 把给定区间\([l, r]\)的颜色全部变成\(c\)，2. 将所有颜色为\(c\)的元素的值都加上\(x\)，3. 查询一个位置，给出他现在的值。

题解

看到序列赋值可以想到ODT，但是本题还有一个对所有颜色的增加值的操作。由于颜色的范围是\(1-n\)，我们可以记录每个颜色被加的总权值，最后询问的时候再加上。但是这样做会有一个问题：如果颜色改变了，是不能加上在此之前增加的新颜色的值的，而且之前被加的颜色的值也无法加上。

我们考虑改变颜色后会对区间造成的影响：首先，新颜色已经被加的值是不能叠加到这个区间的，我们考虑把它减去，这样询问的时候我们加上这个颜色的值，就能弥补被多减去的值，使得答案正确。其次，之前的颜色的值我们也可以在询问时加上，这样答案就正确了。所以对于询问，我们回答的是当前颜色所有累加的值和之前由于颜色变动的影响，我们需要维护这样的影响。

下面引出了数状数组的一个用法：可以用来“区间修改”。这里的区间修改不是改变单点那样的赋值，因为真正这么做时间复杂度是\(O(n\log n)\)的，我们所谓的区间赋值是利用前缀和的思想，且只能回答区间和。考虑到树状数组我们可以完成对于\([1,l]\)的和的查询，所以对于区间和的查询是sum[r] - sum[l-1]，即类似前缀和的查询，同时，由于树状数组的前缀和查询是按照lowbit(x)规则往下求和的，所以我们对这个区间整体修改\(+x\)，可以对\(l\)这个点加上\(x\),对\(r+1\)这个点减去\(x\)，这样查询当前区间的时候由于前缀和，当前区间的和其实就增加了\(x\)（不是对区间的每个数都\(+x\)导致区间总和增加\((r - l + 1) * x\)），当前区间之前的位置没有影响，而对于\(r\)之后的位置，由于又被减掉了\(x\)所以是没有影响的。总之，通过这样的操作，我们实现了区间修改。设\(c_i\)表示之前的颜色，\(c_j\)表示被修改成的颜色，\(sum_{c}\)表示颜色\(c\)被累加的和，那么我们对于\(l\)位置加上\(sum_{c_i} - sum_{c_j}\)，对于\(r+1\)位置加上\(sum_{c_j} - sum_{c_i}\)即可。

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
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
#define int long long

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) { init(n_); }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) { return sum(r) - sum(l); }

    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << (int)std::log2(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    map<int, int> f;
    f[0] = 0;
    Fenwick<int> bit(n);
    vector<int> color(n);
    while (q--) {
        int l, r, c, x;
        l--;
        auto split = [&](int x) -> void {
            auto it = prev(f.upper_bound(x));
            f[x] = it->second;
        };
        string op;
        cin >> op;
        if (op[0] == 'C') {
            cin >> l >> r >> c;
            l--, c--;
            split(l);
            split(r);
            auto it = f.find(l);
            while (it->first != r) {
                bit.add(it->first, color[it->second] - color[c]);
                bit.add(next(it)->first, -color[it->second] + color[c]);
                it = f.erase(it);
            }
            f[l] = c;
        } else if (op[0] == 'A') {
            cin >> c >> x;
            c--;
            color[c] += x;
        } else {
            cin >> x;
            x--;
            split(x);
            cout << bit.sum(x + 1) + color[f[x]] << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Atcoder Beginner Contest 371 F

给定\(n\)个人，每个人站在一个位置，现在给出\(q\)次操作，每次操作把一个人移动到一个位置，且移动后不能有人在同一个位置且所有人的相对位置不能改变。输出操作完后所有人移动步数的最小值。

题解

显然贪心是成立的，如果要让第\(i\)个人移动到\(G\)位置，我们还需要考虑路程上其他的人。因为\(i\)到达\(G\)，那么我们需要检查\(x_i\)到\(G\)是否有人，如果有一个人，还要检查到\(G+1\)，假设除了\(i\)还有\(m\)人需要移动，那么需要检查到\(G + m\)，把\(x_i,x_{i+1},...x_{i+m}\)分别设置为\(G,G+1,...G+m\)，形成一个等差数列。

这看似是一个区间赋值操作，但是很难完成：因为每个数不是相等的，而是形成等差数列的，我们最希望的是能把每一个数都赋值成相等，于是想到了对于等差数列的一个处理：\(a_i - i\)，这是因为\(a_i\)与\(a_j\)形成公差为1的等差数列，必有\(a_i = a_j +(j - i)\)，即\(a_i - i = a_j - j\)。所以我们选择把每一个数一开始的位置减去\(i\)，这样，对于每次第T个人移动到G，我们让G也减去T，这样，每一个需要移动的数都会移动到G，可以区间赋值操作了。

还有一个需要考虑的要点是怎么找到需要修改的位置。考虑到在减去\(i\)之前，需要检查到\(G\)，所以减去\(i\)后，需要检查到\(G - i\)，如果第二个数需要被赋值，那么应该检查到\(G + 1 - (i + 1) = G - i\)，如果需要检查第\(m+1\)个数，那么应该检查到\(G + m - (i + m) = G - i\)。可见，位置减去\(i\)的操作不仅便利了区间赋值，对于判断位置也让我们更加简单。

我们使用ODT维护，分别处理向左或向右移动的情况，如果向左的话，\(\Sigma|a_i - G| = \Sigma a_i - \Sigma G\)，向右的话则相反。

还要注意一些细节，向右处理是不难的，计算当前区间左端点到右端点的距离更新即可，然后删除这段区间跳到下一个区间即可，主要问题在于向左处理，由于我们维护的区间是从左到右的，所以删除区间的时机变得比较难把握：首先，第一次寻找区间的时候不能删除，需要特判，而接下来的操作我们需要删除掉右边的区间，这样需要在循环结束后再删除一次，所以，我们还需要特判当前区间位置恰好等于G的情况，此时不能删除。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, q;
    cin >> n;
    int ans = 0;
    map<int, int> f;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        v -= i;
        f[i] = v;
    }
    f[-1] = -9e15;
    f[n] = 9e15;
    f[n + 1] = 9e15;
    cin >> q;
    while (q--) {
        auto split = [&](int x) -> void {
            auto it = prev(f.upper_bound(x));
            f[x] = it->second;
        };
        int t, g;
        cin >> t >> g;
        t--, g -= t;
        auto it = prev(f.upper_bound(t));
        if (it->second < g) {
            split(t);
            it = f.find(t);
            while (it->second < g) {
                ans += (next(it)->first - it->first) * (g - it->second);
                it = f.erase(it);
            }
            f[t] = g;
        } else if (it->second > g) {
            split(t + 1);
            it = f.find(t + 1);
            auto prv = prev(it);
            int x = prv->first;
            bool ok = 0;
            while (prv->second > g) {
                x = prv->first;
                ans += (it->first - prv->first) * (prv->second - g);
                auto tmp = it;
                it = prv;
                prv = prev(prv);
                if (!ok) {
                    ok = 1;
                } else {
                    f.erase(tmp);
                }
            }
            f.erase(it);
            f[x] = g;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}