珂朵莉树(区间赋值平衡树)

珂朵莉树是一种建立在有序容器之上的区间数据结构,又名老司机树(ODT)。它把一段连续且取值相同的下标合并为一个节点存储,只要题目含有把整段区间统一赋值(推平)的操作且数据随机,就能获得极高的均摊效率。

概述

该结构因某道以角色珂朵莉命名的竞赛题目而流行于算法竞赛圈。它用一个有序集合维护若干形如左端点、右端点、区间值的三元组,区间之间互不重叠且覆盖整个序列。其效率的关键前提是存在区间推平操作,使区间总数在随机数据下不会膨胀。

核心原理

• 区间存储:每个节点表示一段值相同的连续区间,以左端点作为有序集合的键。
• 分裂操作:处理任意区间前,先在两个端点处把跨越边界的节点切开,得到严格对齐的边界。
• 推平操作:把某区间内所有节点删除,合并为单个新节点,这是控制节点数量的关键。
• 复杂度依赖数据:在含推平且数据随机时区间数期望为对数级,均摊近似高效;但可被恶意数据卡到退化。

应用场景

珂朵莉树主要用于算法竞赛中含有大量区间赋值、区间加、区间第k大或区间求幂和等混合操作的题目。当题目保证数据随机或明确存在推平操作时,它以简洁代码替代复杂的线段树写法,是一种典型的以数据分布换效率的技巧。

常见问题

问:珂朵莉树的复杂度可靠吗?答:它的高效严格依赖存在推平操作且数据随机;若出题人针对性构造数据不含推平,区间数会退化,复杂度失去保证。

问:它能替代线段树吗?答:不能通用替代,只有在满足推平前提的特定题型下才优;缺乏该前提时应使用线段树等有严格复杂度保证的结构。