数据结构

可持久化数据结构是指在每次修改后都保存了修改前版本的数据结构。在可持久化数据结构中，我们可以很方便的追溯到某次修改前的版本，以此来完成某些操作。简单来说，对于nnn次插入操作，我们就存储nnn个版本，第iii个版本对应了前iii次操作后的数据结构。当然，不可能真的存nnn个完全独立的版本，空间会直接爆炸(～￣▽￣)～。可以注意到，对于Trie和线段树等数据结构来说，每次插入只改变了一条链上的节点，因此对于每次插入操作，我们只需要新建这条链上的节点，而其他的节点可以直接白嫖上一个版本的。 常用的可持久化数据结构主要有可持久化的Trie和可持久化线段树。 可持久化Trie 首先，既然有nnn个版本，当然就对应了nnn个根节点，从不同的根节点开始遍历就可以得到不同版本的数据结构。下面简单演示一下可持久化Trie的插入过程。 最开始是一个空的Trie，插入一个字符串no（黑色节点表示根节点） 然后插入一个字符串game，由于这整个字符串都属于要改变的节点，所以都要新建，同时，为了从新建的根节点能够访问到以前插入的字符串，新的根节点也要有边连向n 继续再插入一个字符串no，但是no之前已经插 ...

Splay树，即二叉伸展树，是一种非严格平衡的二叉搜索树，由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明（摘自百度百科）。相比与AVL、红黑树而言，Splay树不需要额外地存储平衡信息，因此显得更为简洁，代码实现也较为简单（指150行代码），同时具有很强的扩展性，常用于算法竞赛中。 至于我为什么突然想要学Splay树，因为这是Tarjan发明的……没错，就是求强连通分量、割点、桥的Tarjan算法的那个Tarjan。事情的起因是我最近刚学完强连通分量，然后查了一下Tarjan的资料，发现原来是祖师爷级别的大佬，拿过图灵奖，发明了很多图论的重要算法和数据结构。于是就对Splay树产生了兴趣，虽然这玩意已经明显超过了我的算法水平（刚学完强连通的蒟蒻），但我还是自不量力毅然决然地花了两天手搓了Splay，然后又花了一天的时间调试。 那么废话了那么多，接下来正式介绍Splay树 （以下内容和代码部分抄袭参考自oiwiki和其他人的博客、文章等） （图片均使用开源网站ioDraw绘制，感谢开源者的贡献） 基本成员 S ...

最近花了两天时间学了下树状数组，然后感觉堪比玄学，故写篇文章总结一下。 2024.08.07 UPD：添加了树状数组的树形结构解释，与树状数组上二分。 树状数组（binary indexed tree），也叫BIT，又以其发明人名字被称为Fenwick树。树状数组利用二进制下标来维护区间和，能够做到以log⁡n\log{n}logn的复杂度进行单点修改和区间求和，同时配合差分数组等结构，还能做到区间修改、单点查询和区间修改、区间查询等功能，相比与线段树来说更为简单和优雅。 基本知识 树状数组最为重要的一个设定就是lowbitlowbitlowbit——二进制最低位的1及其后面的0所组成的数字，相比与前缀和，树状数组的每一位维护的是(i−lowbit(i),i]\left(i-lowbit(i),i\right](i−lowbit(i),i]的区间和，比如6，二进制为110，那么这一位维护的就是原数组6到4100的区间和（不包含4）。 那么要如何计算一个数的lowbitlowbitlowbit呢？如果用一个1作为check来判断每一位是否是1，那么代码大概长这样： 1234for(in ...