数据结构笔记，知识点+例题分析

chaynflow · 2023-01-07 17:35:23 · 个人记录

树链剖分（重链）

思想：把树“剖”成一条条不相交的链路。

先定义一些概念：

1. 重儿子：非叶节点儿子中以它为根子树节点最多的一个儿子。

2. 轻儿子：非叶节点的除重儿子以外的儿子

3. 重边：连接两个重儿子的边

4. 重链：连续的重边形成的链

5. 轻边：除重边外的边

6. 链头：重链中深度最小的点

剖好的链的重要性质：任意点到根节点的路径上，轻边数量\le log_2 n。证明？略。。。。。。

基本用法：LCA

如何求LCA(x,y)?

1. 如果x与y在同一重链，LCA(x,y)=y

2. 否则，如果de_x < de_y，交换x,y，并执行fa[top[x]]，让x跳到上一层重链,重复第一步。

程序实现3步：

void dfs1(int u, int p)
{
    fa[u] = p;
    de[u] = de[p] + 1;
    sz[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v]; // 计算子树大小
        if (sz[v] > sz[son[u]])
            son[u] = v; // 计算重儿子
    }
}

void dfs2(int u, int h)
{
    top[u] = h;
    if (!son[u]) return; // 没儿子
    dfs2(son[u], h); // 重儿子的链头跟自己一样
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == son[u] || v == fa[u]) continue;
        dfs2(v, v); // 轻儿子的链头是儿子自己
    }
}

void lca()
{
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        while (top[x] != top[y]) // 跳到为同一条重链为止
        {   
            if (de[top[x]] < de[top[y]]) swap(x, y); // 把x放到链头较深的重链上
            x = fa[top[x]]; // 穿过轻边，去到上一条重链
        }
        cout << (de[x] < de[y] ? x : y) << endl;
    }
}

二叉查找树/平衡树/BST

fhq treap(别问我为啥是这个最先）

treap,即tree+heap,基于二叉查找树与堆的结合体。

每个节点分配两个属性，键值(key)与优先级(pri)。

fhq treap基于两个基本操作：分裂(split)与合并(merge)。

split:

定义为void Split(int u, int v, int &lt, int &rt) 。

作用，将以u为根的子树按键值v分裂，返回以lt与rt为根的两棵子树。

void Split(int u, int v, int &lt, int &rt)
{
    if (u == 0) 
    {
        lt = rt = 0;
        return;
    }
    if (t[u].key <= v)
    {
        lt = u;
        Split(t[u].rs, v, t[u].rs, rt);
    }
    else
    {
        rt = u;
        Split(t[u].ls, v, t[u].ls, lt);
    }
}

merge:

定义为void Merge(int x, int y) 。

作用，将以x与y为根的子树按优先级合并，返回新树的根。

int Merge(int x, int y)
{
    if (x == 0 || y == 0) return x + y;
    if (t[x].pri > t[y].pri)
    {
        t[x].rs = merge(t[x].rs, y);
        return x;
    }
    else
    {
        t[y].ls = merge(x, t[y].ls);
        return y;
    }
}