颜色段均摊的线段树写法

robinyqc · 2024-12-05 16:03:57 · 算法·理论

机房用小肠写代码的大神 @GMJoanna 发现线段树也能写 odt，我感觉确实。故记录下来。

前置知识：区间推平（颜色段均摊），ODT。

区间推平：指的是对 [L, R) 进行某些查询，然后将 [L, R) 设置为相同值的操作。例子。

下面假定你会了 ODT，然后我们下面用线段树实现相似的操作：找到每个被删除的颜色段，然后将他们的颜色设置为某个颜色。

考虑线段树当前节点为 [l, r)，如果全部是同一个颜色，那么返回，否则递归两个子树。由于线段树递归是先左再右的，所以可以顺序找到即将删除的区间。这个做法和 Segment Beats 是一样的复杂度分析，就是，每个颜色段提供 O(\log n) 的势能，总共 O(n + m) 个颜色段，所以复杂度为 O(n\log n)。

具体找到一个被删除的区间的做法是，维护两个变量 l 和 c，表示当前最后一个颜色段是从 l 开始的，颜色为 c。当线段树上找到一个颜色完全相同的区间时，如果该区间颜色和 c 一样就合并，否则 l\gets \text{当前区间的左端点}，c \gets \text{当前区间的颜色}。

于是做完了。感觉上常数是很小的，实际上测试后发现差不多，甚至线段树有时候比较慢。下面是一些测试数据（单位：秒，程序 A 是 map 实现，程序 B 是线段树实现）。

• 随机数据：

  Results for program A:
  Mean: 0.788355, Variance: 0.072245, Std Dev: 0.268784, Range: 1.068930, Median: 0.776874
  Results for program B:
  Mean: 0.994135, Variance: 0.144233, Std Dev: 0.379781, Range: 1.479207, Median: 1.002931

• 单点修改（这种也可以卡链表写法）：

  Results for program A:
  Mean: 0.704929, Variance: 0.240140, Std Dev: 0.490040, Range: 1.690491, Median: 0.508689
  Results for program B:
  Mean: 0.284956, Variance: 0.031118, Std Dev: 0.176404, Range: 0.608953, Median: 0.229302

这个测试在我的 github 仓库上有，感兴趣可以去看看，如果有更好的写法可以找我。代码我在洛谷剪贴板也放了一份。