珂朵莉树：修订间差异
（→适用范围） 标签：移动版编辑 移动版网页编辑 |
小无编辑摘要 |
||
| 第1行： | 第1行： | ||
'''珂朵莉树'''，又称Old Driver Tree(ODT)<s>（老司机树），</s>是一种基于std::set的'''暴力'''数据结构。 | '''珂朵莉树'''，又称Old Driver Tree(ODT)<s>（老司机树），</s>是一种基于std::set的'''暴力'''数据结构。 | ||
=== 适用范围 === | ===适用范围=== | ||
在'''{{color|red|数据随机}}'''的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。 | 在'''{{color|red|数据随机}}'''的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。 | ||
'''时空复杂度''' | === '''时空复杂度''' === | ||
珂朵莉树的复杂度是由assign_val保证的。 | 珂朵莉树的复杂度是由assign_val保证的。 | ||
由于数据随机，有1/4的操作为assign。 | 由于数据随机，有1/4的操作为assign。 | ||
set的大小快速下降，最终趋于logn | set的大小快速下降，最终趋于logn ，使得这种看似暴力无比的数据结构复杂度接近O(mlogn) | ||
== 引用 == | |||
洛谷题解 https://www.luogu.com.cn/problem/solution/CF896C | |||
讲解 https://www.bilibili.com/video/av21651173 | |||
2020年7月7日 (二) 22:32的版本
珂朵莉树，又称Old Driver Tree(ODT)（老司机树），是一种基于std::set的暴力数据结构。
适用范围
在数据随机的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。
时空复杂度
珂朵莉树的复杂度是由assign_val保证的。
由于数据随机，有1/4的操作为assign。
set的大小快速下降，最终趋于logn ，使得这种看似暴力无比的数据结构复杂度接近O(mlogn)