珂朵莉树 - 时砾逐光

致敬传奇出题人lxl

珂朵莉树起源于CF896C ，这道题要求我们实现一种数据结构，可以较快地实现区间和、区间赋值、求区间第 k 大值和求区间 n 次方和。

使用场景

珂朵莉树是一种技巧，而不是一种特定的数据结构，可以用map实现也可以用set等实现，适用于区间赋值操作的数据结构题，在数据随机的情况下复杂度极其优秀，但如果数据不随机且出题人针对数据结构构造了特殊数据，那么复杂度会严重退化。

结构实现(set)

struct Node_t {
  int l, r;
  mutable int v;

  Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}

  bool operator<(const Node_t &o) const { return l < o.l; }
};

这里v被声明为mutable，这是因为在set中，元素是const的，无法修改。但我们需要在split操作中修改v的值，所以使用mutable来解除const限制。

核心操作-split

split操作是珂朵莉树的核心，它的作用是将包含pos位置的区间分裂成两个区间：[l, pos-1]和[pos, r]。这样我们就可以精确地对任意区间进行操作。

auto split(int pos) {
    auto it = s.lower_bound(Node_t{pos, 0, 0});
    if (it != s.end() && it->l == pos) {
        return it;
    }
    it--;
    int l = it->l, r = it->r;
    int v = it->v;
    s.erase(it);
    s.insert(Node_t(l, pos - 1, v));
    return s.insert(Node_t(pos, r, v)).first;
}

s.lower_bound(Node_t{pos, 0, 0})：找到第一个左端点 大于等于 pos 的区间。
if (it != s.end() && it->l == pos)：如果找到了一个区间且这个区间的左端点就是pos，那么我们无需分裂，直接返回该区间的迭代器。
it--：如果没找到，说明pos在某个区间内部，我们需要回退一个迭代器，找到包含pos的那个区间。
s.erase(it)：删除原来的大区间。
s.insert(Node_t(l, pos - 1, v)) 和 s.insert(Node_t(pos, r, v))：将被删除的区间分裂成两个小区间并插入回set中。
返回pos所在的新区间的迭代器。

核心操作-assign

assign操作用于将区间[l, r]的值全部修改为v。这是珂朵莉树保证复杂度的关键操作，因为它能将多个小区间合并成一个大区间，从而减少set中的元素数量。

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(Node_t(l, r, v));
}

auto itr = split(r + 1), itl = split(l);：顺序很重要！ 必须先split(r + 1)再split(l)。因为如果先split(l)，返回的迭代器itl可能会在split(r + 1)时因为set的修改而失效。通过split操作，我们将区间[l, r]独立出来。
s.erase(itl, itr)：删除[l, r]范围内的所有旧区间。
s.insert(Node_t(l, r, v))：插入一个代表整个[l, r]的新区间。

其他操作

在实现了split和assign之后，其他的区间操作就变得非常简单了。我们只需要利用split将要操作的区间[l, r]独立出来，然后遍历这个区间内的所有小块进行操作即可。

区间加

void add(int l, int r, int val) {
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; ++it) {
        it->v += val;
    }
}

查询区间第k小

int query_kth(int l, int r, int k) {
    auto itr = split(r + 1), itl = split(l);
    std::vector<std::pair<int, int>> vec;
    for (auto it = itl; it != itr; ++it) {
        vec.push_back({it->v, it->r - it->l + 1});
    }
    std::sort(vec.begin(), vec.end());
    for (auto p : vec) {
        k -= p.second;
        if (k <= 0) {
            return p.first;
        }
    }
    return -1; // 或其他未找到时的返回值
}

查询区间幂次和

long long query_pow_sum(int l, int r, int p, int mod) {
    auto itr = split(r + 1), itl = split(l);
    long long res = 0;
    for (auto it = itl; it != itr; ++it) {
        res = (res + (long long)(it->r - it->l + 1) * pow(it->v, p, mod)) % mod;
    }
    return res;
}

// 需要一个快速幂函数
long long pow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

结构实现(map)

除了set，我们也可以用map来实现珂朵莉树。map的key可以存储区间的左端点l，value可以存储区间的右端点r和值v。

#include <map>
#include <utility>

// key: 左端点
// value: {右端点, 值}
std::map<int, std::pair<int, int>> odt;

核心操作-split

map版本的split与set版本类似，但操作map的迭代器和元素的方式有所不同。

auto split(int pos) {
    auto it = odt.upper_bound(pos);
    if (it != odt.begin()) {
        auto prev = std::prev(it);
        if (prev->first < pos && pos <= prev->second.first) {
            auto& [r, v] = prev->second;
            int old_r = r;
            r = pos - 1;
            return odt.emplace(pos, std::make_pair(old_r, v)).first;
        }
    }
    return it;
}

核心操作-assign

assign操作同样是先split再合并。

void assign(int l, int r, int v) {
    auto itr = split(r + 1);
    auto itl = split(l);
    odt.erase(itl, itr);
    odt[l] = {r, v};
}

其他操作

与set版本类似，在map版本中，我们同样利用split函数来划定操作区间，然后遍历这个区间内的所有节点来完成相应操作。

区间加

void add(int l, int r, int val) {
    auto itr = split(r + 1);
    auto itl = split(l);
    for (auto it = itl; it != itr; ++it) {
        it->second.second += val;
    }
}

查询区间第k小

int query_kth(int l, int r, int k) {
    auto itr = split(r + 1);
    auto itl = split(l);
    std::vector<std::pair<int, int>> vec;
    for (auto it = itl; it != itr; ++it) {
        vec.push_back({it->second.second, it->second.first - it->first + 1});
    }
    std::sort(vec.begin(), vec.end());
    for (auto p : vec) {
        k -= p.second;
        if (k <= 0) {
            return p.first;
        }
    }
    return -1;
}

查询区间幂次和

long long query_pow_sum(int l, int r, int p, int mod) {
    auto itr = split(r + 1);
    auto itl = split(l);
    long long res = 0;
    for (auto it = itl; it != itr; ++it) {
        res = (res + (long long)(it->second.first - it->first + 1) * pow(it->second.second, p, mod)) % mod;
    }
    return res;
}

// 快速幂函数与set版本相同

复杂度分析

珂朵莉树的复杂度依赖于assign操作的次数。在数据随机的情况下，assign操作会使得区间数量大大减少，因此复杂度接近于O(n loglog n)，其中n是操作次数。然而，在最坏情况下（没有assign操作），split操作会不断增加区间的数量，复杂度会退化到O(n log n)，甚至更差。

split(pos): O(log n)，其中n是set中的元素数量。
assign(l, r, v): O(k log n)，其中k是[l, r]范围内的区间数量。由于assign会合并区间，所以均摊复杂度很低。
其他操作: O(k log n)，其中k是[l, r]范围内的区间数量。