珂朵莉树

    来自中国珂学院
    HGGG（讨论 | 贡献）2020年7月7日 (二) 22:32的版本

    珂朵莉树，又称Old Driver Tree(ODT)（老司机树），是一种基于std::set的暴力数据结构。

    适用范围

    在数据随机的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。

    时空复杂度

    珂朵莉树的复杂度是由assign_val保证的。

    由于数据随机，有1/4的操作为assign。

    set的大小快速下降，最终趋于logn ，使得这种看似暴力无比的数据结构复杂度接近O(mlogn)

    引用

    洛谷题解 https://www.luogu.com.cn/problem/solution/CF896C

    讲解 https://www.bilibili.com/video/av21651173

    取自“https://wiki.sukasuka.cn/index.php?title=珂朵莉树&oldid=17882”