数据结构学习笔记

DS!

基础线段树

不必多言。

典中典的有：区间和，区间最值，区间 $0,1$ 个数，区间连续（交错） $0,1$ 个数，区间加，区间乘。

最需要注意的就是 pushdown ，一定要考虑 tag 之间的互相影响。

除了单纯的 DS 题之外，还常常用于优化 DP。

不要搞忘 build。

基础树状数组

维护单点改，区间和；区间加，单点值。后缀最值。

常数超级小。之前树状数组 $O(n\log^2 n)$ 把线段树二分 $O(n \log n)$ 吊起来打 （

区间加区间和：转化为差分，然后求前缀和的前缀和。

线段树的高科技

权值线段树

把节点换成了权值，可以用于求解全局第 $k$ 大。

线段树合并&分裂

$O(n \log n)$ 合并 $n$ 颗有 $1$ 个节点的线段树，常用于树套树。

可持久化线段树

既可以拿来记载区间历史版本，也可以拿来询问静态区间的第 $k$ 小。

思想就是每次修改操作新加入一条链而不是重新建一颗线段树。

树套树

线段树套平衡树

比如线段树套平衡树，可以维护区间第 $k$ 小。

线段树套权值线段树

维护区间颜色。

二维线段树

你说得对，但这个东西复杂度是假的，要么用二维树状数组，要么用线段树套线段树。

zkw 线段树

Waiting to update.

吉老师线段树

Waiting to update.

李超线段树

Waiting to update.

平衡树

有很多，但是只需要记得 Treap,Splay 就可以了。

常用于求解全局的排名问题，不过有时候可以被 std::set 平替。

是一颗倒悬的 Splay

LCT

waiting to update.

KD-Tree

waiting to update.

分块

优雅的暴力。

这玩意真的是数据结构吗

线段树想不出来的题可以试试分块。

莫队

一种利用分块的离线的奇妙做法。

这玩意好像也不是数据结构

用莫队冲过去的题一般正解都是平衡树，主席树之类的。

思想就是把询问按照块来排序然后双指针。