数据结构总结
树状数据结构
树状数组
树状数组上的每个节点\(i\)维护了从\(i-lowbit(i)+1\)到\(i\)的信息，其中\(lowbit(i)\)表示\(i\)二进制下最低位的1，大致如图：
树状数组本身可以支持单点修改和区间查询，可以维护满足结合律和可差分的信息，如加减法和异或等。如果用来维护差分可以做到区间修改单点查询。树状数组的树高时\(O(\log n)\)的，而且操作均可以用循环实现，常数很小。如果要维护区间加区间查询，需要维护\(\sum\limits_{i} a_i\)和\(\sum\limits_{i}i\times a_i\)。
树状数组也可以支持维护二维信息，最常见的是但单点加，子矩阵查询，也可以通过维护\(a_{i,j},a_{i,j}\times i,a_{i,j}\times j,a_{i,j}\times i\times j\)来维护子矩阵加子矩阵查询。
线段树
线段树应该是应用最广的树形数据结构之一，可以在\(O(\log n)\)的时间内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
线段树是一颗二叉树，每个节点\(x\)维护了一个区间\([l,r]\)，这个点的左儿子\(2x\)维护了区间\([l,mid]\)，右儿子\(2x+1\)维护了区间\([mid+1,r]\)。容易发现，线段树的树高也是\(O(\log n)\)的，不过注意最多会有\(4n-5\)个节点，因此空间要开到4倍。线段树在查询时的主要优化就是如果当前区间\([l,r]\)完全被查询的区间\([L,R]\)包含，那么就直接返回答案，这样可以保证每次询问的区间最多被拆成\(O(\log n)\)个这样的区间，那么询问的复杂度也是\(O(\log n)\)的。如果要涉及到区间修改，就需要引入懒标记，因为如果每次修改都递归到最底层的话复杂度时\(O(n)\)的，这时我们就需要通过延迟对信息的修改来降低复杂度。每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问（修改或查询）带有标记的节点时才进行。
动态开点线段树
如果线段树不需要一开始就把树建好，那么我们可以动态开点，即每个点的左右儿子的编号不一定时\(2x,2x+1\)，而是需要用\(ls,rs\)来维护，而且我们只有访问到一个节点时才建立代表这个区间的节点，这样就可以让空间是\(m\log n\)的。
权值线段树
顾名思义，就是线段树的节点维护的是权值的信息，一般配合动态开点使用。
可持久化线段树
可持久化线段树可以维护线段树的历史版本。由于线段树的单点修改一次最多只会修改\(O(\log n)\)个节点，那么我们新的版本只会有\(O(\log n)\)个节点和上一个版本不一样，因此我们只需开新节点存下这些修改了的位置，剩下的直接继承前一个版本的节点，这样就可以把时间和空间都做到可以接受的范围。
可持久化权值线段树
即主席树，可以维护不带修区间权值相关的信息，如静态区间第k小、区间mex、二维数点、两个排列区间交等。
平衡树
平衡树是一种二叉搜索树，并且满足一个点左子树内的点的权值都小于它，一个点右子树内的点的权值都大于它，但是为了让树高在\(O(\log n)\)范围，不同种平衡树使用了不同是方法。一般的平衡树都可以维护、插入、删除、查全局前驱、后继、第k大、排名等信息。
Splay
Splay 树, 或伸展树，它通过 Splay操作 不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，能够在均摊 \(O(\log n)\) 时间内完成插入，查找和删除操作，并且保持平衡而不至于退化为链。
FHQ Treap
和treap一样，fhq treap是通过给每个节点随一个权值，然后按这个随机权值判断两棵子树何合并为同一颗子树，本质是利用了随机的特性使得树高期望是\(O(\log n)\)的。fhq treap主要操作时split和merge，split是把整棵树按一个权值分裂成两棵树，merge是把两棵树按随机权值合并。而且由于每次操作最多影响\(O(\log n)\)个节点，因此可以可持久化。
树套树
树状数组套主席树
首先是树状数组套主席树，可以维护带修改的普通主席树维护的信息，如带修区间第\(k\)大，因为主席树的本质还是维护前缀信息，刚好可以配上树状数组，这样时间复杂度是\(O(n\log^2n)\)的。
线段树套平衡树
线段树套平衡树就是对线段树的每个节点用一颗平衡树来维护信息，可以维护区间查全局前驱、后继、第k大、排名等信息。运用线段树可以把询问的区间拆成\(O(\log n)\)个，然后再在这些区间的平衡树上查询信息，这样可以在\(O(\log^2n)\)~\(O(\log^3 n)\)时间内解决。
01Trie
01Trie是一种可以高效维护异或问题的数据结构，本质就是把数字的二进制从高到低丢到Trie里，并且由于每次只会修改\(O(\log n)\)个节点，所以可以可持久化。
块状数据结构
分块，本质是把序列分成长度为\(B\)的块，可以维护一些不支持合并的信息，一般会分成整块和散块，修改时整块打标记，散块暴力改，修改时一样，复杂度一般由怎么平衡复杂度决定。