树链剖分与主席树整理:(拙作)

树链剖分
定义

树链剖分就是将树分割成多条链，然后利用数据结构（线段树、树状数组等）来维护这些链.

需要了解的东西:

• 重儿子：子树结点数目最多的结点；
• 轻节点：父亲节点中除了重结点以外的结点；
• 重边：父亲结点和重结点连成的边；
• 轻边：父亲节点和轻节点连成的边；
• 重链：由多条重边连接而成的路径；
• 轻链：由多条轻边连接而成的路径；

图片解析:被黑链连起来的点是重结点(就是图中没有标记红点的,图中标记红点的点是轻结点) 2 ~ 11 是重链,4 ~ 14 是重链.

每个点的编号是dfs序.
dfs序
定义
就是这颗树被dfs遍历到的顺序.

这张图的dfs序为A-B-D-E-G-C-F-H

算法大致需要进行两次的DFS，第一次DFS可以得到当前节点的父亲结点（faz数组）、当前结点的深度值（dep数组）、当前结点的子结点数量（size数组）、当前结点的重儿子（son数组）(不难看出重链内的节点编号是连续的,所以可以用数据结构来维护这个数组)

void dfs1(int u, int father, int depth) {
    /*
     * u: 当前结点
     * father: 父亲结点
     * depth: 深度
     */ 
    // 更新dep、faz、siz数组
    dep[u] = depth;
    faz[u] = father;
    siz[u] = 1;
​
    // 遍历所有和当前结点连接的结点
    for (int i = head[u]; i; i = edg[i].next) {
        int v = edg[i].to;
        // 如果连接的结点是当前结点的父亲结点，则不处理
        if (v != faz[u]) {
            dfs1(v, u, depth + 1);
            // 收敛的时候将当前结点的siz加上子结点的siz
            siz[u] += siz[v];
            // 如果没有设置过重结点son或者子结点v的siz大于之前记录的重结点son，则进行更新
            if (son[u] == -1 || siz[v] > siz[son[u]]) {
                son[u] = v;
            }
        }
    }
}

第二次DFS的时候则可以将各个重结点连接成重链，轻节点连接成轻链，并且将重链（其实就是一段区间）用数据结构（一般是树状数组或线段树）来进行维护，并且为每个节点进行编号，其实就是DFS在执行时的顺序（tid数组），以及当前节点所在链的起点（top数组），还有当前节点在树中的位置（rank数组）。

void dfs2(int u, int t) {
    /**
     * u：当前结点
     * t：起始的重结点
     */
    top[u] = t;  // 设置当前结点的起点为t
    tid[u] = cnt;  // 设置当前结点的dfs执行序号
    rnk[cnt] = u;  // 设置dfs序号对应成当前结点
    cnt++;
​
    // 如果当前结点没有处在重链上，则不处理
    if (son[u] == -1) {
        return;
    }
    // 将这条重链上的所有的结点都设置成起始的重结点
    dfs2(son[u], t);
    // 遍历所有和当前结点连接的结点
    for (int i = head[u]; i; i = edg[i].next) {
        int v = edg[i].to;
        // 如果连接结点不是当前结点的重子结点并且也不是u的父亲结点，则将其的top设置成自己，进一步递归
        if (v != son[u] && v != faz[u]){
            dfs2(v, v);
        }
    }
}

　主席树(本人的拙见)

主席树(本文乱YY的.)
创造者(HJT)话:想法是对原序列的每一个前缀[1..i]建立出一颗线段树维护值域上每个数的出现次数，然后发现这样的树是可以减的，然后就没有然后了.

主席树可以用来解决如下问题：“给出一列数,a1,a2…an,每次询问其中连续的一段区间ai到aj其中的第K大的数是多少？”(询问次数为5000,序列长度≤2e5)

我们应如何做呢.
每次询问排序??显然复杂度是巨大的
那么接下来我们要学习主席树(一个可持续化数据结构)

可持续化:能够查询历史版本.

何谓查询历史版本: 例如我们执行一些操作:
你还剩下1,1,1,2,2这些牌.假设你打出了对二(当然,现实生活中是不会有人这样出的)然后你发现你手里有三张一样的牌,然后你想撤销以前的操作,然后你就回到刚开始的时候.这在我们编程里怎样体现呢.就是存起以前的状态.然后进行一些撤销操作之类的.这就是查询历史版本.
想要学会主席树.我们还要学会
* 权值线段树 :
前缀和.

权值线段树

来了解一下权值线段树吧.
与线段树相差无几,唯一的不同之处就是他的(数组)下标为x的数组所存的值是数组中有当前值的数的个数
例如我们有这么一些数: 1.2.3.4.4.3.2.1
假设我们要 求出5 ~ 8这个区间的第三大数.
我们就会构造这么两个图

现在我们来模拟一下如何查询[5,8]第三大数.

首先我们对比一下根节点的左孩子的个数,我们会发现4 - 2 = 2 ,2 < 3,所以相比以前的版本多出了两个元素,因为我们要找第三大.所以我们去右孩子去找第k大元素,直到根为止.
这就是前缀和的思想.但是我们要找这么多区间.每一次都要造一个[1,i] (i不确定)的区间.然后去查询,显然空间复杂度是巨大的.
接下来我们要开始正式学习主席树啦.
这样空间是过不去的,然后我们就会发现他们有很多共同的信息.
例如:、

1、建立
首先建立一棵空的线段树，也是最原始的主席树，此时主席树只含一个空节点，然后依次对原序列按某种顺序更新，即将原序列加入到对应位置。此过程时间复杂度为O(M),空间复杂度为O(M*log(M))。如图：

2、更新
更新时按照自己的离散值寻找对应位置，信息域data+1。我们知道，更新一个叶节点只会影响根节点到该叶节点的一条路径，故只需修改该路径上的信息域data。每个主席树的节点即每棵线段树的结构完全相同，只是对应信息域data不同（可以理解为线段树的结构完全一样，只是对应叶子节点取值不同，从而有些节点的信息域data不同，本质是节点节点不同），此时可以利用历史版本，即利用相邻的上一棵线段树的信息。相邻两颗线段树只有当前待处理的元素不同，其余位置完全一样。因此，如果待处理的元素进入线段树的左子树的话，右子树是完全一样的，可以共用，即直接让当前线段树节点的右子树指针指向相邻的上一棵线段树的右子树；若进入右子树，情况可以类比。此过程容易推出时间复杂度为O(log(M))，空间复杂度为O(log(M))。如图：

3.查询
由于主席树每个节点是棵线段树，信息域、结构相同，可以相减。这是主席树查找的关键所在。例如查找第k小的元素，若左子树信息域data之差大于等于k，则直接到左子树查找；否则调整k值即减去左子树的信息域data之差，然后到相应的右子树查找。由于是线段树属于二叉树结构，故整个过程的时间复杂度为O(log(M))，M往往是原问题离散化后的数据数量级。对于任意主席树的节点即某棵线段树，其含义再次说明一下，存储的是原序列的某个前缀：a[1]、a[2]…a[k]，其中k小于等于M，所以主席树节点i、j信息域data相减得到的即为原序列在区间[i,j]上的信息域data。此过程时间复杂度为O(log(M))，。