珂朵莉树

Preface

珂朵莉树（Chtholly Tree）起源于CF896C，那道题要求我们实现一种数据结构，可以较快地实现：

区间加、区间赋值、求区间第k大值、求区间n次方和

就此需求来说，普通的树状数组、线段树等显然难以胜任，看上去需要一种相当复杂的数据结构。

然而，在出题人的题解中，实现的数据结构却很简单，最初用自己的 ID 把这种数据结构命名为 ODT，后又改名为珂朵莉树。

珂朵莉树的适用范围是有区间赋值操作且数据随机的题目。其实珂朵莉树看上去并不像是树状数据结构，

但因为一般要用到有序集合，而有序集合是用红黑树实现的，所以也不算名不副实。

在随机数据下，珂朵莉树可以达到 O(nloglogn) 的复杂度，参见这篇文章（这篇文章博主也是非常厉害的)。

而我接触这个特殊的数据结构是因为同学推荐力扣每日一题用这种方法实现，起到一个抛砖引玉的效果。

C++ 实现参考：https://zhuanlan.zhihu.com/p/106353082
Rust 实现参考：http://heavensheep.xyz/?p=276

本篇后续实现方式为 Java，利用的数据结构是 TreeSet，底层实现也是红黑树。

Details

有序集合

在介绍 ODT 之前，先按照朴素做法取实现，采用有序集合，去判断各种情况的发生以及如何处理，

并且利用底层插入寻找结点的时间复杂度为 O(logn) 来解决这道问题，但是实现起来非常复杂，细节很多，

我在按照这种方法去实现时，一直在调试，详情参考： LeetCode 官方题解

我在具体实现时候也优化了一些代码逻辑并且添加了 comment，便于理解，参考代码如下：

class RangeModule {
    // 利用 TreeMap, 表示 intervals, 注意是半开区间
    TreeMap<Integer, Integer> map;

    public RangeModule() {
        map = new TreeMap<>();
    }
    
    public void addRange(int left, int right) {
        // 利用 TreeMap 性质找到第一个严格大于 left 的 entry
        Map.Entry<Integer, Integer> entry = map.higherEntry(left);

        // 如果存在 entry, 寻找小于 left 的 entry; 反之, 取最后一个 entry
        Map.Entry<Integer, Integer> start = (entry != null ? map.lowerEntry(entry.getKey()) : map.lastEntry());

        // 如果当前区间包含 [left, right), 不需再操作
        if (start != null && start.getValue() >= right) {
            return;
        }

        // 如果当前区间的右值小于 right, 更新 [left, right) 为 [l, right), 并移除 [l, r]
        if (start != null && start.getValue() >= left) {
            left = start.getKey();
            map.remove(start.getKey());
        }

        // 以上操作已经处理好最大小于 left 的 entry, 现在更新其后的区间
        while (entry != null && entry.getKey() <= right) {
            right = Math.max(right, entry.getValue());
            map.remove(entry.getKey());
            entry = map.higherEntry(entry.getKey());
        }
        map.put(left, right);
    }
    
    public boolean queryRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = map.higherEntry(left);
        Map.Entry<Integer, Integer> start = (entry != null ? map.lowerEntry(entry.getKey()) : map.lastEntry());
        // 存在并且区间满足即返回 true
        return start != null && (start.getValue() >= right);
    }
    
    public void removeRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = map.higherEntry(left);
        Map.Entry<Integer, Integer> start = (entry != null ? map.lowerEntry(entry.getKey()) : map.lastEntry());
        
        // 如果当前区间重叠 [left, right)
        if (start != null && start.getValue() >= right) {
            if (start.getKey() == left) {
                map.remove(start.getKey());
            } else {
                map.put(start.getKey(), left);
            }
            if (start.getValue() != right) {
                map.put(right, start.getValue());
            }
            return;
        } else if (start != null && start.getValue() > left) {
            map.put(start.getKey(), left);
        }

        // 删除后续区间
        while (entry != null && entry.getKey() < right) {
            map.remove(entry.getKey());
            if (right < entry.getValue()) {
                map.put(right, entry.getValue());
            }
            entry = map.higherEntry(entry.getKey());
        }

    }
}

玛朵莉树

ODT 核心函数只有两个，split() 和 assign()，前者用于分割区间，后者用于区间赋值，也是其精髓。

思路如下：

用一个结构体或者类存储区间信息：左端点，右端点以及区间值
split() 函数用于分割区间，因此需要在开始初始化一个涵盖数据范围的区间
assign() 函数用于区间赋值以及区间合并，使得零散的区间变得整齐

可以参考下图例子，加以理解具体操作：

具体代码如下：

class RangeModule {
    int N = (int)1e9;

    TreeSet<Node> set = new TreeSet<>();

    // Node 需要实现比较器接口
    class Node implements Comparable<Node> {
        int left, right, val;

        public Node(int left, int right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }

        @Override
        public int compareTo (Node o) {
            return this.left - o.left;
        }
    }

    public Node split(int pos) {
        Node node = set.ceiling(new Node(pos, 0, 0)); // 获取大于等于 pos 的结点
        // 如果 node 左边界等于 pos
        if (node != null && node.left == pos) {
            return node;
        }

        if (node == null) {
            // 如果不存在大于等于其的结点, 取最后一个结点
            node = set.last();
        } else {
            // 初始化时插入结点为 [0, N], 故存在 lower
            node = set.lower(node);
        }
        
        // 移除此结点 并新增分割后的结点
        int left = node.left, right = node.right, val = node.val;
        set.remove(node);
        set.add(new Node(left, pos, val));
        node = new Node(pos, right, val);
        set.add(node);

        // 返回分割后右侧结点
        return node;
    }

    public void assign(int left, int right, int val) {
        // 如果使用迭代器需要注意先 split right, 否则不需考虑顺序
        Node end = split(right), begin = split(left);
        // 清空范围内的所有结点, 因为范围内区间可能已经被细分
        while (set.ceiling(new Node(left, 0, 0)).left < right) {
            set.remove(set.ceiling(new Node(left, 0, 0)));
        }
        // 加入新结点
        set.add(new Node(left, right, val));
    }

    public boolean check(int left, int right) {
        Node rNode = split(right);
        Node lNode = split(left);
        // 判断区间内是否均满足
        while (lNode.left < rNode.left) {
            if (lNode.val != 1) {
                return false;
            }
            lNode = set.higher(lNode);
        }
        return true;
    }

    public RangeModule() {
        // 初始化必不可少, 因为后续需要区间分割
        set.add(new Node(0, N, 0));
    }

    public void addRange(int left, int right) {
        assign(left, right, 1);
    }

    public boolean queryRange(int left, int right) {
        return check(left, right);
    }

    public void removeRange(int left, int right) {
        assign(left, right, 0);
    }
}

Final

思考

保持算法高效的核心在于哪里？

除了有序集合本身红黑树高效的插入查询之外，还在于 assign 函数清理掉细碎的小区间，合并成大区间，

这样提高了 query 也就是查询操作的效率，有点 GC 的感觉
为什么 C++ 实现 assign 中需要先 split right ?

这是因为迭代器的原因，先左再右可能会导致迭代器失效，因为修改了 left iterator，

上述 Java 代码中，就不需要考虑此问题，有兴趣可以自行更换下顺序，看看代码执行结果，

这里我本身理解也是浅尝则止，是以后需要学习跟进的地方，有关红黑树的实现
最开始初始化一个区间是否必须？

必须，因为后续操作需要操作区间，并且必须是涵盖所有测试数据范围的区间
为什么和官方解法的运行时间差距很大？

因为官方题解是遇到一个新区间或者删除时才会去处理结点，而玛朵莉树是相当于在分裂和合并，

随着操作的增加，结点数也在增加，固然时间就增加，并且后者有很多 new() 操作，

附上学到的一个术语：ad-hoc：指先用低成本实现一个简单易理解的算法，如果后续发现瓶颈再去优化

Ad hoc is a Latin phrase meaning literally ‘to this’. In English, it typically signifies a solution for a specific purpose, problem, or task rather than a generalized solution adaptable to collateral instances

拓展

既然抛砖引玉入门了这道题目，再回到原本的出处CF896C，还剩下三个操作没有实现，具体实现就是暴力，

附上 C++ 伪代码，实现步骤很简单，如果对于上述过程都理解了，自然也就明白了。

区间加

l r x : For each i such that l ≤ i ≤ r, assign ai + x to ai.

void add(ll l, ll r, ll v)
{
    auto end = split(r + 1);
    for (auto it = split(l); it != end; it++)
        it->v += v;
}

区间第 K 小值：

l r x : Print the x-th smallest number in the index range [l, r], i.e.

the element at the x-th position if all the elements ai such that l ≤ i ≤ r are taken

and sorted into an array of non-decreasing integers. It’s guaranteed that 1 ≤ x ≤ r - l + 1.

ll kth(ll l, ll r, ll k)
{
    auto end = split(r + 1);
    vector<pair<ll, ll>> v; // 这个pair里存节点的值和区间长度
    for (auto it = split(l); it != end; it++)
        v.push_back(make_pair(it->v, it->r - it->l + 1));
    sort(v.begin(), v.end()); // 直接按节点的值的大小排下序
    for (int i = 0; i < v.size(); i++) // 然后挨个丢出来，直到丢出k个元素为止
    {
        k -= v[i].second;
        if (k <= 0)
            return v[i].first;
    }
}

区间值求幂的和

l r x y : Print the sum of the x-th power of ai such that l ≤ i ≤ r, modulo y, i.e.

$\sum_{i=l}^{r}{a_i^x}\bmod y$

ll sum_of_pow(ll l, ll r, ll x, ll y)
{
    ll tot = 0;
    auto end = split(r + 1);
    for (auto it = split(l); it != end; it++)
        tot = (tot + qmi(it->v, x, y) * (it->r - it->l + 1)) % y; // qmi 快速幂
    return tot;
}

补充

在学习过程中，也接触到一对名词：在线算法（online algorithm）和离线算法（offline algorithm)

维基百科举了这样一个例子，选择排序是离线算法，而插入排序是在线算法。

那就从这两个算法来看看在线算法和离线算法的区别：

选择排序是不断地从未排序的元素中找到最大（小）的元素放到排序序列的起始位置，

插入排序是不断将未排序的序列插入到有序的序列中，有序序列中的元素相对位置会在一定程度上被改变，

两种排序的本质区别在于，后面的操作对前面操作的结果是否有影响。

更直观地讲，就是离线算法途中拿出来的结果就是最终结果的一部分，

而在线算法可能到了最后一步才能得到需要的结果，

而过程中产生中间结果都是为最后结果的输出而服务的。

数据结构与算法

#数据结构

珂朵莉树

https://eminem-x-github-io.vercel.app/2022/06/22/数据结构与算法/珂朵莉树/

作者

Yuanhao

发布于

2022年6月23日

许可协议

Gin-Swagger 上一篇

人生七年下一篇