Update

直到某天我做到了一道叫 WBLT 的题我才发现 lxl 早在 114514 年前就已想出了这个想法并且成功弄成了平衡树……

这又让我想到了刚学莫队的时候发现自己以前经常采用的优化暴力方法即为最朴素的莫队算法。

唉如果哪一天我也可以创造出一种新算法就好了……

以下为原文章。

---

在这里简单记录一下最近想到的有关 DST 的想法。

关于 DST

DST，是 Dynamic Segment Tree （动态线段树）的简称。（好吧这个名字是我瞎取的）

这是我在前几天做一道题的时候，瞎想出来的。这几天上文化课的时候整理了一下想法，差不多是这样。

首先 DST 能做的，就是在支持所有线段树可以做的操作的基础上，支持链表式的插入和删除。

看下面这个问题：

初始给出一个序列，接着有若干操作。操作一共有以下三种：

• 1 p val 表示在 $p$ 和 $p+1$ 之间插入一个值为 $val$ 的元素。
• 2 p 表示删除 $p$ 位置的元素，并且将它右侧的所有元素向左平移一格。
• 3 l r 表示询问区间 [l,r] 之内的元素和。

DST 就是来解决这类问题的。

这个时候你可能就要问了： 上面这个问题不就是 Splay 板子题么？

没错，这道题对于 Splay 而言就是板子题。而且引用巨佬 sqy 的话：“线段树能做的 Splay 都能做”，所以至少在我现在能想到的范围内，DST 能做的任何事 Splay 都能做。

（听起来这个算法真是逊爆了）

所以我现在先把这个想法记在这里，也许以后我能想到一些好的用法。

内容

由于仅是笔记，而且该数据结构尚且处于初期，这里只给出一个大概的思路。

正如他的名字动态线段树，就是在线段树的基础上加上“动态”。

这个动态指的是线段树每个节点的区间是动态的。

这里用类似动态开点线段树的方法，将每个节点左右区间和左右儿子四个信息都单独存起来。

插入

insert(x,val) 表示在 $x$ 号点的右侧插入值为 $val$ 的节点。

我们先用正常线段树上查找 $x$ 点的方法查找到 $x$ 点的位置，将原来 $x$ 点的区间从 $[x,x]$ 改为 $[x,x+1]$，然后新建两个点 $x$ 和 $x+1$ 作为它的左儿子和右儿子。

然后对于刚才找 $x$ 点过程中经过的链上的所有节点，让他们的右区间 $+1$，然后对于该链以右的部分，打上一个 $lazyTag$ move +1 表示这部分需要向右平移一个单位。

删除

删除与插入类似，对于 $erase(x)$ 查找到 $x$ 的位置后将其删除，然后将整条链上的节点的右区间 $-1$，再给链以右的部分打上 move -1 的 $lazyTag$。

---

上面两个操作的时间复杂度均为 $O(h)$，其中 $h$ 为线段树层数。

为什么这么说呢，因为这个线段树会随着大量点的插入和删除变得不平衡，在极端数据下甚至会退化成链。

（读这句话的时候，有没有想到 BST）

所以我认为这个神奇的 DST，其实跟 BST 很类似，在大量的插入和删除过程中会变得不平衡。

我们知道由于 BST 容易不平衡，所以设计出了那么多种平衡树算法。所以我的直觉告诉我这个 DST 应该也是可以用让他维持平衡的方法的。

---

啥，你问我就算 DST 平衡了，它有什么优点？

我也不知道，也许在以后我能够对其进行增强，又或者这个想法就鸽在这里了。

所以我先记在这里，也许哪天会用得到。