树专题

        之前说过的，来写个树专题，我会把我想到的与树有关的知识点都写一下，当然得是我会的……
        这里讲的东西有些是一笔带过，以后可能会独立写一篇来描述相关算法。
        树，就是不存在环的联通图，通常来说树的边数=点数-1，顺便提一句，还有种叫仙人掌的东西，就是所有边至多在一个环上的图。一棵有根树，就应该有一个树根，除根外每个节点都有父亲节点，除叶子节点外每个节点都有儿子节点。树的深度定义为树根深度为1，其他节点深度为其父节点+1。
        二叉树，就是每个节点最多有两个儿子的树，如果一棵二叉树除叶子节点外每个节点都有两个儿子，且每个叶子节点深度都一样，那它就是满二叉树（或者说一棵深度为k，且有2k-1个节点的二叉树），至于完全二叉树，就是由满二叉树在最深一层从右向左地删除节点的方式生成的二叉树（或者说每一个结点都与同深度的满二叉树中编号从1至n的结点一一对应的二叉树），路径什么的我就不费力解释了……
        树的遍历：
        先序遍历：按树根，左子树，右子树的顺序递归遍历。        中序遍历：按左子树，树根，右子树的顺序递归遍历。
        后序遍历：按左子树，右子树，树根的顺序递归遍历。
        ①树状数组：
        我把它归进来，仅仅是因为它名字里带“树”，我并不认为它跟树有什么太大关系……
        这个数据结构用一个附加数组c来实现对原数组的区间求和，区间求极值，单点修改什么的。我们设一个函数f(x)=(-x)&x，这里-x表示x的补码，&表示与运算，其实表示的是x二进制数码中从右开始的第一个1的位置。对于附加数组中下标为y的位置记录的是从原数组中下标为y-x+1到y的值。例如1号点管辖[1,1]，2号管辖[1,2]，3号管辖[3,3]，4号管辖[1,4]……
        然后，假如我们要查询下标为p的节点的前缀记录值，则ans(p)=ans(p-f(p))∪c[p]，可以用循环来处理，直到p=0，这里∪要根据实际需要决定（求和就是+，最大值就是max等），区间求值的话，其实就是两个前缀值的“差”。
        单点修改的时候，对于下标p，同样是循环，先修改附加数组中的p，每次修改后将p加上f(p)，直到p越界，也是挺好理解的。
        每种操作复杂度都是O(log n)。
        ②线段树：
        用一颗树中的节点来覆盖原数组的区间，根节点覆盖[1,n]，根节点的左儿子覆盖[1,(n+1)/2]，右儿子覆盖[(n+1)/2+1,n]……对于覆盖区间[l,r]的点，记mid=(l+r)/2，其左儿子覆盖[l,mid]，右儿子覆盖[mid+1,r]。
        当我们要查询的时候，从根节点开始，一层一层向下传就是了，比如查询[a,b]，如果当前节点的mid不在[a,b]中，就直接传递给左儿子或右儿子，否则分别传递[a,mid]，[mid+1,b]给左右儿子。当然，如果[a,b]已经是本区间的[l,r]了，那就直接返回当前记录值了。
        插入区间（即区间修改），我们要么可以一层层传递，暴力修改到叶子节点，然后更新整棵树，但这样复杂度较高。如果当前修改区间恰好是当前节点的覆盖区间，我们可以打一个标记，表示这个节点被修改过，等下次查询时，如果查到这个点，就将标记下传，并进行合并（多标记合并时注意考虑优先级），然后复杂度会大幅降低。同时，多种多样的标记然线段树可以做很多很多事情，很多时候是可以取代树状数组的。
        线段树可以进行持久化处理。持久化，简单的说就是你可以访问以前的，或说某次修改之前的线段树，而不一定得是当前得线段树。最简单的思路就是在每一个时间都建一颗树，但是考虑到每修改一个点，产生影响的只有log n个点，我们可以只新建这log n个点，并连接原树中未被修改的儿子。由于每次会产生一个新的根，所以用一个数组来记录每次的根节点，就能实现持久化的查找。
        ③二叉搜索树：
        二叉搜索树是相对于链表的一种优化的查询方法，把整个原数组变成一棵二叉搜索树，树的中序遍历构成原数组的单调数列，每次查询就从根节点出发，判断其与根节点的大小关系，向其左或右子树查询，以此类推。二叉搜索树在数据较特殊时会退化成一条链（当然，可以用随机化），最坏复杂度仍是O(n)，这时需要对其进行旋转操作，使之平衡，于是诞生了平衡二叉树。
        ④平衡二叉树：
        平衡二叉树，即在二叉搜索树的基础上，用各种方式使树尽可能平衡的数据结构，它主要依赖于旋转操作：
        左旋：将根节点的右儿子变成新根，原根变成新根的左儿子，新根的原左儿子变成原根的新右儿子，并作相应调整。
        右旋：与左旋相反就是了。 
        treap（树堆）：treap的主要思想是给树上的每个节点随机一个优先级，在维护二叉树性质的同时，按优先级维护堆性质（至于堆，我们待会再说）。这样一来这颗树能尽可能保持平衡，以保障复杂度。
        Splay（伸展树）：Splay主要依赖于其把一个点旋转至根的操作。每对一个点进行一次修改，查询等操作，就需要将其旋转至根，这样可以保障均摊复杂度控制在O(log n)，相关证明这里不加详述。有一点必须注意，旋转操作应采用双旋而非单旋。即假如当前节点与其父节点同为左子树或同为右子树时，应先将以祖父节点为根的树进行旋转，再将当前节点旋转至根，这样可以使尽可能多的点被移动，使树更加平衡。同时，Splay还有划分，合并，翻转等诸多拓展应用，还被用于LCT中的Auxiliary Tree的维护。
        AVL树：这个树的话，我觉得是最“正宗”的平衡树了。它会时时检测树中是否有某节点左右子树的深度差大于1，一旦大于1，先找到最先发生不平衡的节点，进行旋转，好像也最好理解。
        SBT：其实它和AVL树有些类似，只不过AVL树用深度维护平衡，SBT用size域，即子树大小来维护平衡，它要求每颗子树大小不小于其兄弟节点的儿子为根的子树大小。维护的size域事实上在查询时也有一定用处，每个操作复杂度都是O(log n)。
        红黑树：树上每个节点都有一个颜色，红或黑，根和叶子节点都为黑色，每个红色节点的两个子节点都是黑色，从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。通过对节点的调整和颜色修改维护以上性质，使红黑树的复杂度同样只有O(log n)。
  ⑤堆：
        堆是一种完全二叉树结构，以小根堆为例，每个节点拥有一个key值，我们必须维护每个节点的key值小于其两个儿子的key值，这样一来，根节点就是整棵树中key值最小的，从而可以实现动态修改和查询极值。利用对数组堆进行排序，可得到复杂度与快排相当的O(nlog n)的堆排序算法，也可用于最短路迪杰斯特拉算法的优化。
        左偏树，亦称可合并堆，此时它是普通的二叉树，而非完全二叉树，我们在堆的基础上定义一个右深度：无右儿子的点右深度为0，否则为其右儿子的右深度+1，左偏树要求一个点的左儿子右深度不小于其右儿子的右深度，从而整棵树大部分点集中在左边，亦称左偏树。左偏树支持合并操作，将根的key较小的树作为被插入树，较大为插入树，把插入树的极右链（从根一直向右走的链）上的点依次在被插入树的极右链上找到自己的位置，插入并维护左偏树的性质。可以看出，左偏树并不是一种很平衡的树，有时它甚至很不平衡，因为左偏树本身就不是为了快速查找设计的，它仅仅为了快速对堆进行合并，从而实现一些普通堆难以做到的功能。
        此外，堆还有斐波那契堆，配对堆等拓展，这里不加详述。
 ⑥树上倍增
        树上倍增可以用来快速查询两个节点之间的最近公共祖先，查询路径和或极值等。对于每个点，我们需要维护该点（设为p点）向上2^k条边的祖先f[p][k]，预处理时可以利用f[p][k]=f[f[p][k-1]][k-1]这一公式，同时维护该路径上的和、极值等数据。在查询时，对于两个节点，先把它们提到同一高度，再利用循环移动到它们最近公共祖先的两个子节点，就可以完成查询。        ⑦最小生成树：
        最小生成树，即在一个给定图上，找出一棵生成树，使其边权和最小，相关算法我在另一篇日志已经写过，这里不加详述。        ⑧最优比率生成树：
        与最小生成树相似，但要求是使边权和除以边花费和的比值最大，详见我的另一篇日志。        ⑨树形DP：        树形动态规划，其实就是以树为基础，按树的特定遍历顺序（拓扑序，DFS序等）进行动态规划，亦不难理解。
        ⑩并查集：
        这是一种类似动态链表的结构，它可以实现两棵树的快速合并和两点是否在同一树上的查询。每个点维护其父亲节点的位置，查找时只需递归计算出当前点所在树的根，判断两个根是否相等。合并时以同样的方式，连接这两棵树的根节点。合并时采用启发式合并（较小的树合并到较大的树上面），查询时采用路径压缩（即不记录父亲节点，直接记录树根），可以使效率有所提升。
        可持久化并查集，就是用可持久化线段树维护可持久化树组，实现可持久化的并查集……这话很溜，慢慢品味……
        ?trie（字典树）：
        trie主要用于字符串查询，或有关二进制码的运算。对于字符串，建一个树根，不带任何信息，对每个字符串，我们从根出发，看看根的儿子中是否包含该字符串的第一个字符，如果有，递归到这个子节点处理下一个字符，否则建立一个新的子节点，同样进行处理。对于二进制运算，尤其以异或操作为例，将原数的01串以与字符串相同的方式插入，查询时，就可以从树根出发，寻找与当前数字01位置相反或相同的子节点，就可以得出原树所有数字中与待查询数字异或后的极值。
        PS：trie在字符串匹配算法——AC自动机中有重要作用。
        ?树链剖分：
        顾名思义，就是把树链进行分解，每个点的儿子中子树较大的点称为重儿子，重儿子与父节点的连边称为重边，由重边连成的链称为重链。树链剖分其实就是维护每条重链的记录数据，在查询时优先对查询路径利用重链进行“跳步”，从而达到降低复杂度的目的。其实它和树上倍增很类似，解决的问题也有相同点，个人来说，倍增可能比树链剖分好写一些。
         ?最近公共祖先查询：
        刚才说过的树上倍增就可以用于最近公共祖先查询，这里介绍一种离线的方法：从树根开始，对于每个点，依次递归其子树，递归完毕后，利用并查集把它的子树的集合的父亲设为当前节点。然后找一下每一个与当前节点有关的询问，如果这个询问的另一个节点已经被递归查询过了，那么答案就是另一节点所在集合的父节点。这个方法非常巧妙，但由于是离线，比较麻烦，实际使用较多的还是倍增。
         ?K-d树：
         K-d树主要可以用于解决k近邻查询问题，我们以二维中的最近邻（就是在二维平面的点集上，与给定点的欧氏距离最小）为例。首先对于点集，我们先算出它们x，y坐标的方差，取较大的方差（这是为了使点尽可能分散开），以x轴为例，按横坐标排序，取中位数，作一条与x轴垂直的直线，把所有点分成两个部分，左空间，和右空间，再递归处理这两个空间，将点集建成了一棵树。查询时，递归找出给定点所在的空间，从叶子节点开始，实时更新最小的欧氏距离，查询该点以这个距离为半径画圆是否与当前节点作出的直线相交，如果不相交，则最近邻不可能在另一空间，否则再递归处理另一空间，最后得到的距离即是最小距离。扩展到k近邻也很容易，只需维护一个距离数组就行了。
         ?Link-Cut Tree（动态树）：
         动态树（LCT）是用于维护森林中树的合并，分离等等操作，与树链剖分相同，它也有重边，重链之分，但重儿子的定义为该子树中最后访问的节点。每一条重链用一个Splay来维护（这是为了快速进行合并，删除等操作）。
        Access(x) 操作是动态树的最基本操作，即依次访问树根到点x路径上的所有点。这时，我们需要先Splay(x)，除去x的右儿子（从而除去比x更深的树链，因为我们访问了x，那么x就没有重儿子了）。然后依次对访问到的点进行Splay操作，将其右儿子更换为其后继，直到树根。
        find-root(x) 操作要求找到x的所在根，先Access(x)，然后需要Splay(x)，查询其极右节点就好了
        Cut(x) 断掉x与其父亲的边，先Access(x)，Splay(x)，再断掉x与其左儿子的边就行。
        Link(x,y) 连接x，y点分别对x，y进行Access和Splay操作，对x所在树进行reverse（翻转）操作，再连接x与y。
        以后想到什么再补充吧……