【笔记】珂朵莉树

转载自珂朵莉树学习笔记 - Studying Father’s blog

珂朵莉树（Chtholly Tree），又名老司机树（Old Driver Tree, ODT），是一种非常暴力的维护序列信息的数据结构。

其通过维护值相同的连续段来保证效率，在特殊构造的数据下会退化为普通暴力算法。

Part 1 前置知识

熟练掌握 std::set 的用法。

没了？没错。

Part 2 一个例子

CF896C 是一个非常经典的模板题，珂朵莉树也正是来源于本题。

下面是题面部分：

你需要维护一个序列，并支持如下几种操作：

1. 给区间 [l,r] 内的所有数字加上 x。
2. 将区间 [l,r] 内的所有数字赋值为 x。
3. 求区间 [l,r] 内所有数字中第 x 小的数字（重复数字多次计算）。
4. 求$ ∑_{i=l}^r a_i^x\mod y $ 的值。

题目保证数据随机。

---

前三个操作都不算太难，使用常规的数据结构都可以圆满解决。

问题在于第四个操作。为什么常规的数据结构在第四个操作面前无能为力呢？主要在于其并不能方便地分解为两个子区间的问题。

这时候珂朵莉树就要出场了。

Part 3 正文

Part 3.1 节点结构

我们这样定义一个珂朵莉树的节点：

struct node
{
    int l, r;              //该节点对应的区间
    mutable long long val; //mutable 修饰该变量之后，就可以直接在 set 中修改该变量的值，而不是取出元素修改后再重新插入 set
    node(int L, int R = -1, long long Val = 0)
    {
        l = L, r = R, val = Val;
    }
    bool operator<(const node &a) const
    {
        return l < a.l;
    }
};

接下来，我们定义一个 set<node> odt 来维护一棵 ODT。

Part 3.2 分割区间操作：split

给出一个区间 [l,r] 和一个位置 pos ，怎么把这个区间分割为 [l,pos−1] 和 [pos,r] 两个区间呢？

大致流程很简单：

1. 先在 ODT 中找到含有 pos 位置的区间。
2. 如果 pos 已经是一个区间的左端点，则无需分割。
3. 否则我们把原来的区间删除，插入两个新区间。

详细代码如下：

auto split(int pos)
{
    auto it = odt.lower_bound(node(pos)); //找到左端点不小于 pos 的区间
    if (it != odt.end() && it->l == pos)
        return it; //pos 是区间左端点时无需分割
    it--;          //pos 一定在前一个区间中
    int l = it->l, r = it->r;
    long long val = it->val;
    odt.erase(it); //删除原来的区间
    odt.insert(node(l, pos - 1, val));
    return odt.insert(node(pos, r, val)).first; //插入两个新区间
                                                //这里的返回值是后半段区间对应的迭代器
}

经过这样的分割操作后，容易发现任意两个区间没有相交的部分，这是保证我们接下来操作正确性的前提。

Part 3.3 合并区间操作：assign

如果光分割区间而不合并的话，我们事实上就是对一堆长度为 1 的区间进行操作，珂朵莉树也就会退化为普通暴力算法。

通过合并操作，我们可以迅速降低珂朵莉树的大小，保证珂朵莉树的效率。

这里先给出合并操作的代码：

void assign(int l, int r, long long val)
{
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);         //删除[itl,itr)区间内的所有元素（注意左闭右开区间）
    odt.insert(node(l, r, val)); //将原来的诸多小区间用一个大区间代替
}

注意：在执行 split 操作时，应先 split 右端点，再 split 左端点，否则可能会RE。

通过两次 split 操作，[l,r] 区间内一定都是整段区间。因此我们可以安全地删除原来的零散区间，用大区间代替。

经过 assign 操作后，ODT 的规模会下降不少，从而保证 ODT 的实际运行效率。

Part 3.4 其他操作

所有区间操作都可以套这样的一个模板：

1. 先 split 右端点，再 split 左端点，获得两个端点（左闭右开）的迭代器。
2. 对两个端点之间的所有区间暴力更改。

代码差不多长这样：

void update(int l, int r)
{
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++)
    //do something
}

我们回到那道模板题。

首先是区间加一个值：

void add(int l, int r, long long val)
{
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++)
        it->val += val; //因为 val 被 mutable 关键字修饰，从而可以直接修改 set 里元素的值
}

接下来是区间第 k 小，暴力取出区间内所有段排序一遍即可：

typedef pair<long long, int> pii;
long long kth(int l, int r, int k)
{
    vector<pii> a;
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++)
        a.push_back(pii(it->val, (it->r) - (it->l) + 1));
    sort(a.begin(), a.end());
    for (auto it = a.begin(); it != a.end(); it++)
    {
        k -= it->second;
        if (k <= 0)
            return it->first;
    }
    return -1;
}

然后是区间幂次和，还是暴力，取出区间内所有段累加求和：

long long sum(int l, int r, int x, int y)
{
    long long ans = 0;
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++)
        ans = (ans + fpow(it->val, x, y) * ((it->r) - (it->l) + 1)) % y;
    return ans;
}

注意到我们的区间操作都是直接对值相同的连续段进行处理，当段数较多的时候，效率就会降低。

模板题的完整代码如下：

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#define MOD 1000000007
using namespace std;
struct node
{
    int l, r;
    mutable long long val;
    node(int L, int R = -1, long long Val = 0)
    {
        l = L, r = R, val = Val;
    }
    bool operator<(const node &a) const
    {
        return l < a.l;
    }
};
typedef pair<long long, int> pii;
set<node> odt;
long long a[100005], n, m, seed, vmax;
long long rnd()
{
    long long ret = seed;
    seed = (seed * 7 + 13) % MOD;
    return ret;
}
auto split(int pos)
{
    auto it = odt.lower_bound(node(pos));
    if (it != odt.end() && it->l == pos)
        return it;
    it--;
    int l = it->l, r = it->r;
    long long val = it->val;
    odt.erase(it);
    odt.insert(node(l, pos - 1, val));
    return odt.insert(node(pos, r, val)).first;
}
void assign(int l, int r, long long val)
{
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(node(l, r, val));
}
long long fpow(long long x, long long y, long long mod)
{
    long long ans = 1;
    x %= mod;
    while (y)
    {
        if (y & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}
void add(int l, int r, long long val)
{
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++)
        it->val += val;
}
long long kth(int l, int r, int k)
{
    vector<pii> a;
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++)
        a.push_back(pii(it->val, (it->r) - (it->l) + 1));
    sort(a.begin(), a.end());
    for (auto it = a.begin(); it != a.end(); it++)
    {
        k -= it->second;
        if (k <= 0)
            return it->first;
    }
    return -1;
}
long long sum(int l, int r, int x, int y)
{
    long long ans = 0;
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++)
        ans = (ans + fpow(it->val, x, y) * ((it->r) - (it->l) + 1)) % y;
    return ans;
}
int main()
{
    cin >> n >> m >> seed >> vmax;
    for (int i = 1; i <= n; i++)
    {
        a[i] = rnd() % vmax + 1;
        odt.insert(node(i, i, a[i]));
    }
    for (int i = 1; i <= m; i++)
    {
        int op = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1, x, y;
        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) << endl;
        else
            cout << sum(l, r, x, y) << endl;
    }
    return 0;
}

Part 4 总结

在数据中区间赋值操作较多的时候，珂朵莉树的规模较小，实际运行效率较高。但特殊构造的数据往往并不具有这样的性质，导致其退化为普通暴力算法，因此要结合题目性质来考虑是否使用珂朵莉树来解题。

虽然事实上珂朵莉树在很多题目中都可以用其他常规数据结构代替之，但其简单直接，易于调试的特点让它成为了一个解决不少题目的第二选择。