省选数据结构
- (STL)
- 并查集
- 树状数组
- 线段树
- 平衡树
- (LCT)
- 树套树
- (K-D) 树
(STL)
关键是会用。比较常用的有 (set,multiset,bitset,priority\_qeuue,queue,map) 这几个。
并查集
一定记得要初始化。
优化的方式主要有两种：路径压缩和按秩合并。
如果需要支持撤销，那么只能使用按秩合并。
单独使用其中一个，复杂度是 (O(nlog n)) ；同时使用，复杂度是 (O(nalpha(n))) 。
同时还可以顺带维护一下其他的信息，合并时一同合并即可。
树状数组
一维的树状数组比起线段树的优势就是码量小且常数小，但是功能远不如线段树全面。
同时它可以较为容易的拓展到高维，而二维线段树就已经比较难写了。
比如二维平面上的数点 / 求和。
线段树
经典应用
维护区间内的信息，并支持单点 / 区间修改。如区间加、区间乘、区间和。
如果我们可以在较短时间内将两个区间的信息合并，就可以使用线段树来维护。
动态开点线段树
就是到一个点，如果没有，新建一个节点就好。
可持久化线段树（主席树）
可以存储 (m) 个版本的线段树信息,要求每次修改都只是单点修改,每颗线段树的管辖范围都是 ([1,n]) 。
考虑线段树的一次单点修改操作，影响到的节点只有对应叶子节点到根节点路径上的所有节点。
这些节点数目是 (O(logn)) 的，所以在维护新版本的线段树时，只用新建出这些节点,其它节点沿用上个版本的。
并不用每次都把上个版本的所有节点拷贝出来，因为每个节点只需要知道儿子节点，直接将儿子节点指过去。
显然需要使用动态开点。
经典的使用方法是利用主席树对 ([1,1],[1,2],[1,3]…,[1,n]) 这 (n) 个前缀建出 (m) 颗线段树。
这样在查询可减的信息时（如某数的个数），就可以直接用 ([1,R]) 的线段树答案减去 ([1,L−1]) 的线段树答案了。
线段树分治
(TEST\_20200608 T1)
线段树合并
(K-D) 树
平衡树
可以支持插入 (x) ，删除 (x) ，查询排名，查询第 (k) 大，查询前驱，查询后继。
还可以支持对区间的改动。
（不知道能不能操作区间加之类的操作，求巨佬告知）