ChthollyTree（珂朵莉树）

发表于 更新于 分类于 Valine： 本文字数： 4.2k 阅读时长 ≈ 4 分钟

珂朵莉树（ChthollyTree）又称老司机树（ODT），起源于CF 896C Willem, Chtholly and Seniorious

一位用户Old Driver在给出了线段树的解法后，又发布了一份前所未有的解法，其中利用到的数据结构因此被称为珂朵莉树或老司机树。

其核心就是用二叉搜索树维护一组连续的不相交的区间，初始是覆盖了整个数轴的一个大区间，核心操作只有两个一是split(pos)将整个区间集在pos处断开并返回以pos为左端点的迭代器，assign(l, r, val)将区间[l,r)赋值为val。

先上代码

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
120
121
122
123
typedef long long ll;

template<typename T>
class ChthollyTree {
private:
    struct ChthollyNode {
        ll l, r;
        mutable T w;
        ChthollyNode(ll l, ll r=0, const T& w=T()): l(l),r(r),w(w) {}
        bool operator < (const ChthollyNode& n) const {
            return l < n.l;
        }
    };
    set<ChthollyNode> s;
public:
    ChthollyTree(ll n=1e9+2, const T& v=T()) { s.insert(ChthollyNode(-1, n, v)); }

    auto split(ll pos) {
        auto itr = s.lower_bound(pos);
        if (itr != s.end() && itr->l == pos) return itr;
        --itr;
        auto l = itr->l;
        auto r = itr->r;
        auto w = itr->w;
        s.erase(itr);
        s.insert(ChthollyNode(l, pos, w));
        return s.insert(ChthollyNode(pos, r, w)).first;
    }

    void update(ll l, ll r, function<void(ChthollyNode&)> f) {
        auto right = split(r), left = split(l);
        for(auto itr = left; itr != right; itr++) {
            f(const_cast<ChthollyNode&>(*itr));
        }
    }

    void assign(ll l, ll r, const T& w) {
        auto right = split(r), left = split(l);
        s.erase(left, right);
        s.insert(ChthollyNode(l, r, w));
    }

    void visit(ll l, ll r, function<void(const ChthollyNode&)> f) {
        auto left = s.lower_bound(l);
        if (left == s.end() || left->l != l) --left;
        auto right = s.lower_bound(r);
        for(auto itr = left; itr != right; itr++) {
            f(*itr);
        }
    }

private:
    class ItemAccessor {
    public:
        ItemAccessor(ChthollyTree& ct, ll i): ct(ct), i(i) {}
        ItemAccessor& operator = (const T& x) {ct.assign(i, i+1, x);return *this;}
        ItemAccessor& operator += (const T& x) {ct.update(i, i+1, [x](auto& p){p.w += x;});return *this;}
        ItemAccessor& operator -= (const T& x) {ct.update(i, i+1, [x](auto& p){p.w -= x;});return *this;}
        operator T() const {T r;ct.visit(i, i+1, [&r](auto& p){r = p.w;}); return r;}
    private:
        ChthollyTree& ct;
        ll i;
    };

    class RangeAccessor {
    public:
        RangeAccessor(ChthollyTree& ct, ll b, ll e):ct(ct), b(b), e(e) {}
        void operator = (const T& x) {ct.assign(b, e, x);}
        void operator += (const T& x) {ct.update(b, e, [&x](auto& p){p.w += x;});}
        void operator -= (const T& x) {ct.update(b, e, [&x](auto& p){p.w -= x;});}
    private:
        ChthollyTree& ct;
        ll b;
        ll e;
    };

public:
    // 通过下标访问单点值的语法糖
    ItemAccessor operator [] (ll i) {
        return ItemAccessor(*this, i);
    }

    // 通过下标访问区间值的语法糖
    RangeAccessor operator [] (const tuple<ll, ll>& range) {
        return RangeAccessor(*this, std::get<0>(range), std::get<1>(range));
    }

    T sum(ll l, ll r) {
        T ret = 0;
        visit(l, r, [&](auto& p) {
            ret += p.w * (std::min(p.r, r)-std::max(p.l, l));
        });
        return ret;
    }

    T min(ll l, ll r) {
        bool first = true;
        T ret = 0;
        visit(l, r, [&](auto& p) {
            if(first) {
                first = false;
                ret = p.w;
            } else {
                ret = std::min(ret, p.w);
            }
        });
        return ret;
    }
    
    T max(ll l, ll r) {
        bool first = true;
        T ret = 0;
        visit(l, r, [&](auto& p) {
            if(first) {
                first = false;
                ret = p.w;
            } else {
                ret = std::max(ret, p.w);
            }
        });
        return ret;
    }
};

解释一下几个关键点：

1）ChthollyNode结构体中数据字段w为什么用mutable修饰，原本在对set元素遍历时是不能修改元素值的，因为set底层是一颗红黑树，如果修改值可能导致它不满足二叉搜索树的性质了。但这里比较特殊，这里的区间是不重叠的，仅通过左端点的值来定义结点的序，所以修改w不会影响到序。

2）update和assign的时候为什么都是先取右端迭代器再取左端迭代器auto right = split(r), left = split(l);，因为split可能导致迭代器失效，如果先取了左端点迭代器，右端点可能就在左端迭代器指向的节点上，将它断成两个结点后原迭代器也就是已经拿到的左端点迭代器就失效了。

我在其上进一步实现了常见的区间求和，区间最大最小值，区间赋值，区间自增，单点赋值，单点自增，单点取值。可以发现它和线段树完成了很多相似的操作，但是实现要比线段树简单很多。

更复杂的自定义操作可以通过update和visit传入自定义的操作方式，其中update会调用split断开传入的[l, r)端点，以便执行数据更新，而visit则不会断开区间，只保证迭代的首位区间能覆盖[l, r)，可以用于查询时取数据进行计算。

关于效率，我们可以看到查询操作通过visit完成，不会增加珂朵莉树的复杂程度，而更新操作分两种，一种是区间的统一赋值，通过assign完成通常情况下会减少整体区间的数量，因为它会删除[l, r)上的区间合并成一个，而update操作可能会增加1个或2个区间取决于左右端点是否已经存在。

如果操作和数据是随机的，并且穿插着assign操作，那么珂朵莉树的实际效率会很好，如果操作只用到update和visit，那珂朵莉树会越来越复杂，不过如果查询只是单点仍然可以提供比较好的效率。我实际测试通常要比动态开点线段树的耗时少，甚至在只有update和区间查询最值时实际效率也不差，不明所以。

另外，我们还可以通过珂朵莉树完成线段树不方便进行的操作，比如查询区间内元素的方差。