@数据结构二-个人总结

· · 个人记录

线段树

当发现我们维护的一些值，都是和区间最小值有关，那么我们就可以方便的维护了！

处理区间修改的利器：线段树分治！

我们只需要支持添加修改，撤回使用栈序撤销！

代替树剖的好方法

维护树上倍增信息！

常常用于，不通过树剖在线维护信息，而是使用树剖的结构。

维护链并

维护链并可以用线段树合并+O(1)LCA，这样还可以做更多的事。

在线莫队/在线待修莫队

普通在线莫队的思想其实就是树分块的思想：我们选出\sqrt{n}个关键点，预处理出它们的答案。但是为了转移，我们还需要处理出一些中间信息，比方说区间内某个颜色的出现次数，莫队维护的信息往往有可减性，我们维护每个关键点的前缀的信息即可相减。

待修怎么办？直接做就可以了，每次修改的时候只修改中间数组即可。需要询问的时候如果发现关键点区间是旧的就暴力修改。复杂度同样是O(n^{5/3})

树上相邻点加，维护历史最大值

给定一棵树，支持链加；不在链上且与链上的某点直接相连的点加，求历史最大值。

肯定要树剖，历史最大值实质就是一个pair标记；对于第二种操作，注意到大部分情况下是一个点的所有儿子打tag（除了链延伸下去的一个儿子），那么我们肯定是把标记打在和父亲有关的位置。

注意到我们需要把一条重链（的区间）的所有轻儿子大打tag，如何用数据结构实现？

把所有点按照父亲的dfs（先重后轻）序排序，一条重链的轻儿子就形成了一个区间

所以我们再建一种线段树维护上面的信息即可。

现在的关键是如何把两棵线段树的信息合并在一起。注意到一条链上最多只有log个轻儿子，而重儿子的信息不在第二棵线段树上存，所以我们只需要在走轻边的时候，查一下第二棵线段树上这个轻儿子被打的tag的和即可！（查完就清空tag）

看似两个标记不同步，但是我们发现两种标记“交替”的次数只有log次

HNOI 单旋

平衡树上中序遍历相邻的点，要么前者没有右儿子，要么后者没有左儿子。

对于这道题，我们直接用权值线段树维护值为v的点的深度即可。

链并

每次选出若干个点，把它们到根的链并+v。我们建出虚树，在叶子处+v，对于每个LCA，如果子树里有k个v我们就在这个点-(k-1)v，这样我们不用树剖，只用维护子树和就行了。

很神奇的，似乎可持久化fhqTreap需要用我之前打懒标记的方法才能过。