高级数据结构 -1

· · 个人记录

返璞归真。
持续更新，每天闲的没事大概就会搞这个吧。

1.可持久化线段树2

直接整体二分，分裂的时候保证有序。
然后用双指针前缀和代替树状数组。
时间复杂度 O(n \log n)，空间复杂度 O(n)，常数极小。

使用的数据结构：数组。

2.永无乡

经典重标号，把连通块合并的过程刻画成一棵树。
然后现在问题变成了子树第 k 大。

DFS 一遍把树拍成序列，然后问题变成区间第 k 大。
直接套用问题 1 的做法即可。
时间复杂度 O(n \log n)，空间复杂度 O(n)，常数一般。

使用的数据结构：数组。

3.最大异或和

首先观察到查询是一个类似于最大后缀和的形式。
所以我们对原序列进行前缀异或和，然后问题就变成了区间内选一个数与给定的 x 异或和最大。

显然还是考虑离线下来做。
修改操作啥用没有，事先处理好最后的数组即可。

按位考虑，从高到低枚举二进制位。
每次把序列中的所有数按照这一位划分为左右两部分。
对于一个询问 x，如果存在一个数使得异或之后这一位为 1，那就向这个数所在的部分划分。
否则划分到另一部分，递归处理。

求是否存在可以直接三指针扫一遍。

时间复杂度 T(n) = 2T(\frac{n}{2}) + O(n)，也就是 O(n \log n)，空间复杂度 O(n)，常数极小。

使用的数据结构：数组。

4.左偏树

可并堆是什么高级东西，不会（?）
堆是什么高级科技，不会（?）
数据结构统统不会，直接乱搞。

考虑有个好东西叫启发式合并。
如果我们要维护最小值还不用数据结构的话那大概也就只能排序了。

考虑对于每一个数的集合维护若干个有序数组。
当我们进行合并的时候，枚举每一个有序数组。
记这个数组长度为 |A|，若存在一个数组 |B| 满足 \frac{|A|}{2} \le |B| \le 2|A|，就直接把两个数组归并。
由于两个数组长度只有常数级别的差距，所以可以认为是小的集合的复杂度。

这个东西就类似于启发式合并了吧，所以合并的总复杂度 O(n \log n)。
然后考虑对于一个数的集合，每两个有序数组长度至少翻倍。
所以只会有 O(\log n) 个。
查询/删除最小值的话就直接暴力扫即可。

注意应该降序排序，这样删除的就是最后一个数而不是第一个。

总时间复杂度 O(n \log n)，空间复杂度 O(n)，常数小。
相当于是又发现了一种新的可并堆实现。
如果处理一个 O(\log n) 个数的最小值就可以做到查询 O(1)。
整体复杂度和左偏树完全相同，只不过基于均摊。
不过结构非常简单而且内存访问连续（确信）。

使用的数据结构：数组。