学科夏令营-大鹏展翅飞行最新章节-免费小说-全文免费阅读-大鹏展翅飞行作品-话本小说网

时间大概在学科夏令营那段时间：

当时信息组的其他几个还有新高二的同学都开始学splay了，每天听到zms和yjq（一个学长，很强）讨论splay，还戏称为"spaly"，就感觉很紧张，他们怎么学这么厉害的东西，我还完全不了解。

然后我上网查了查splay，看到几百行的代码，看到什么zig，zag，势能分析（所以说写的这么丑的博客为什么会排前几），就感觉这个东西无法理解，大概看了看也没看懂。

去问了问于神splay的功能是什么——“插入，删除，查询第k小”

反正天天也无聊，于是就想了想：

线段树可以查第k小，只需要让其叶子sorted即可。

所以线段树是不是也能做？

但是我们的线段树是一个静态的结构（当时的想法），这个东西要动态化才行，不然如何插入删除？

线段树维护了每个点的区间，这个东西是静态的，也就是问题所在，我们考虑如何动态化这个东西：

插入一个节点的时候，如果找到了插入位置，那么一定是一个叶子，我们可以给这个节点新建两个叶子的儿子。

可以发现这个插入位置后面的所有节点都进行了平移，于是我们可以考虑对这个进行打标记来维护，称为平移标记，每次push_down平移标记来实现动态化。

每次删除的时候可以使用其兄弟来代替被删除的节点，同理需要进行平移标记的维护。

查询的时候先push_down平移标记，然后考虑是否进入左儿子即可。

可以发现这样的结构在插入链式数据下复杂度会有问题，考虑如何平衡。

我当时第一个想到的是设定一个ratio，使得左右儿子的比例在ratio之内，否则暴力重构，写了写发现好像是对的，去问于神，然后他说这个就是“替罪羊树”......

诶所以我自己发明平衡树了？

这么看来平衡树很简单啊。

这么看来我很强啊（错觉）。

然后我就一直按这个思路想下去了，想了很多种奇怪的写法，比如不平衡的时候合并一下，或者按中点分裂什么的。

我乱写了一个策略，通过了平衡树模板题，但是当时写的非常复杂，因为我维护了父亲，而且写法未经过优化。

后来发现不需要所谓的平移标记，可以直接维护size，这样可以按相对位置二分下去，减少了很多代码量。

发现可以不存father，减少了很多代码量。

又发现这个树也是可以”旋转“的，我们将旋转定义为合并两个节点即可（所以我看到说什么”无旋treap不用旋转，和treap不一样“的言论都感觉很谔谔，因为本身就是等价操作，同一个东西写出来不一样而已）。

同时也是可以分裂的，这里我分裂定义为了经过 O( logn )O(logn) 次旋转使得根的左儿子的右儿子是我们需要的区间。

我发现我设计出的平衡树的确是可以支持所有操作的，复杂度也都是 O( logn )O(logn) ，而且个人认为这个很好写。

所以我发明平衡树了？

当时起了个名字“自平衡线段树”——“Self Balancing Segment Tree”，虽然后来查了很久发现其实是把两个OI界中未引入的东西结合在了一起，应该叫做“Weight Balanced Leafy Tree”

刚做出来的时候觉得这个是很重要的东西，于是对其他人都藏着掖着，生怕同学们学到我的技术，因为我当时也知道，省队就5个名额，同学都是我的竞争对手。

当时mhy听说我的平衡树很强，就问我能不能10分钟写出来，我接受了挑战，然后还真的写出来了，得到了集训队爷的认可+1

当时就对自己充满了自信，我都能发明这么强的一个数据结构，那进集训队保送清华北大还不是随手的事情吗（flag）。