Data Structures

后缀数组

构造后缀数组有两种算法，dc3和倍增，效率分别为O(n)和O(nlogn)，但前者的实现较困难。后缀数组构造后获得了3个数组，sa[i]表示所有后缀排序后的排在第i位的后缀，rank[i]表示原串从第i位到结尾的那个后缀在sa中的排名是多少。height[i]表示sa[i]和sa[i + 1]所表示的字符串的最长公共前缀的长度。

后缀数组的所有后缀中包括空串，因此有strlen(s)+1个后缀。

树状数组

树状数组是一种可以以logN的效率询问数组前x项和修改数组元素的一种数据结构。其原理是在原数组之外再建立一个数组，这个数组的每一位存储的是前面某些项的和，具体是哪些项呢？例如：现在我们求前x项的和，那么就要找到最大的a使得x%（2^a）=0。那么我们就存储原数组中从x-2^a+1 ~ x这些位的和。然而在这个新建的数组中这些位的和可以更容易的表示，因为该块可以被进一步的拆分成一些在新建数组中已经求过和的块。具体实现用lowbit的方法。

具体求a的方法其实就是lowbit嘛。

树状数组常与二分查找共同使用，用来查找对于一个数字k，求前多少位恰好和为k。

树状结构频繁开辟指针空间浪费时间，可以直接开辟节点数组，并让指针指向数组中的未使用位。

线段树

线段树的基本思想，无论是更新还是查询都要遵循一个原则，当线段恰好覆盖一个节点的区间时就直接对该节操作而不再向下操作。绝对不能把区间内所有节点全部一代到底，到叶子节点。

现在遇到的线段树共有如下几种：

1.插入点型

对于这种线段树，通常是向线段树中插入点，即对应一个叶子节点的信息，而线段树中所有节点也都是记录的关于以该点为根的子树中已插入的点的统计信息，询问通常是问线段树中某个区间对叶子节点的统计信息。

2.线覆盖型

对于这种线段树，与第三种有以下共同特点：所有询问和插入操作都是以区间为单位的，每次都是对一个区间进行操作。每个节点通常会用一个变量来记录以它为跟的子树的相关信息，在回溯过程中更新此变量。当操作的区间能完整的覆盖一个节点对应的区间时直接对该节点操作，不再向下操作。

这种线段树还有其独有的特点：当操作一个短线段时，这个短线段在线段树中由上至下运行到自己对应的位置，这个过程中会经过若干个对应长线段的节点，在经过长线段时，要把长线段的节点中的信息移动到其两个直接子节点中，然后再继续向下走。这样可以保证区间信息存储位置的在树中的纵向专一性，即树中节点的直系血亲之间只能有一个点记录信息。

原因如下：在这种线段树的题通常具有一下性质：(1)新插入线段与旧的线段重叠的部分的信息如果纵向分布，不存储在同一个节点中，则在回溯统计子树信息过程很难计算。(2)新插入的线段与旧线段的重叠部分可以只保存新线段信息，这样才能插入过程中完整覆盖一个节点时不用向下操作。

3.线保留型

这种线段树除了与第二种线段树的共同特点外，还有一个重要特性就是即使旧线段与新线段重叠了旧线段中的信息也仍然有意义，或者要求插入的线段必须保持在其插入的位置不向下迭代。

其中保持位置的一种典型情况就是有删除操作。删除并不是随意的删除，每次删除的线段与原来插入的线段相对应，只删除那些曾经插入过的线段。这种通常我们为了删除时候方便，在短线段向下运行经过长线段的过程中不会把长线段向下迭代，因为长线段是要被删除的，如果向下迭代删除时就没有办法对长线段原来的存储节点进行操作，只能对其许许多多的后代节点中的一些（那些被迭代到了的节点）进行操作，复杂度极高。这种线段树的题通常信息纵向分布也是可以回溯计算的。

有时候可能还要综合运用第2、3种线段树。

当要对一棵树的许多子树进行操作时，可以使用时间戳对树进行标记，然后使用线段树对子树进行操作。

树的最小表示

树的最小表示判断同构，

定义S[t]表示以t为根的子树的括号序列

S[t]={‘(‘,S[c1],S[c2],…,S[ck],’)’ (c1,c2,…,ck为t的k个子节点，S[c1],S[c2],…,S[ck]要按照字典序排列)}

为了保证同构的树的括号序列表示具有唯一性，我们必须规定子树点的顺序。按照子树的括号序列的字典序就是一种不错的方法。

若最小表示相同，则两树同构。