Xinyuan Mao

Xinyuan Mao

Math fuels logic, Physics sparks wonder, Coding builds dreams.

数据结构 1

7 minute read

Published:

平衡树 Intro

P3369 【模板】普通平衡树 | P6136 【模板】普通平衡树（数据加强版）

众所周知 BST 是一种非常方便的结构，但是唯一的问题是树高不对。

也就是说，只要树高能一直保持 $O(\log n)$ 就行了，顺着这样的思路，出现了 AVL 和 Treap。

Rotate 操作

Rotate 操作不改变树的中序遍历，即一棵 BST 在任意 rotate 之后还是一棵 BST。基于 rotate 操作我们可以调整树的深度。

AVL

满足每个节点的两个儿子的高度差绝对值 $\le 1$ 的二叉树，树高为 $O(\log n)$。

没啥用，不写了。大致思想就是插入之后不满足上面那个条件的时候，rotate 一下调整。

Treap

把一个长为 $n$ 的序列随机打乱，然后按顺序插入二叉查找树中，那么这颗二叉查找树树高期望为 $\Theta(\log n)$。

没啥用，不写了。好像说 Treap 常数比 Splay 小。

Splay

参考：

简单操作：dir, pushup, rotate

bool dir(int u) {
    // 若 u 为左儿子返回 0，若 u 为右儿子返回 1
    return u == tr[fa[u]][1];
}
void pushup(int u) {
    siz[u] = cnt[u] + siz[tr[u][0]] + siz[tr[u][1]];
    // cnt 为这个节点的大小，即这个节点代表的值出现了几次
}

有了 dir 之后，rotate 就很好实现了：

void rotate(int u) {
    int v = fa[u], w = fa[v];
    bool r = dir(u);

    // 更新树结构 tr
    tr[v][r] = tr[u][!r];
    tr[u][!r] = v;
    if (w) tr[w][dir(v)] = u;

    // 更新对应的 fa
    fa[u] = w;
    fa[v] = u;
    if (tr[v][r]) fa[tr[v][r]] = v;

    pushup(v), pushup(u); // 先 v 再 u
}

splay

接下来介绍 Splay 的核心操作：splay(u, target)，意思是想办法进行 rotate 直到 fa[u] == target。特别地，splay(u) 代表把 $u$ 弄成根，即 fa 是 $0$。

这一段涉及到复杂度分析，所以我们直接背代码：

void splay(int u, int target = 0) {
    while (fa[u] != target) {
        int v = fa[u];
        if (fa[v] != target)
            // fa[u] 已经是 target 的儿子时，不需要这一步
            rotate(dir(u) == dir(v) ? v : u);
            // 若 u,fa[u],fa[fa[u]] 三点共线，转 fa[u]；否则转 u
        rotate(u); // 不管怎么样都要转 u
    }
    if (!target)
        root = u;
}

根据老师的 PPT，$n$ 个点执行 $m$ 次 splay 的复杂度是 $O((n+m) \log n)$。也就是说均摊下来是 $\log$ 的。

也正因为此，我们接下来的功能设计都要围绕 splay 操作展开。切记每次操作做完的时候都把当前的节点 splay 上去。飞起来！

警告：Splay 和无旋 Treap 之类的树不同，Splay 实现时各种操作互相耦合，需要整理好逻辑。我的整体逻辑借鉴了朝夕的文章（在上面的参考文章当中）。TODO: 如果以后发现了更好的实现逻辑会更新过来。

ins

插入一个元素。

void ins(Val k) {
    if (!root) { // 树是空的，新建一个根
        root = ++tot;
        val[root] = k;
        cnt[root] = 1;
        pushup(root);
        return;
    }

    int u = root, v = 0; // v 一直保持是 u 的父亲
    while (true) {
        if (val[u] == k) { // 树里已有这个值
            cnt[u]++;
            pushup(u), pushup(v);
            splay(u); // 飞起来！
            return;
        }
        bool r = k > val[u];
        v = u, u = tr[u][r];
        if (!u) { // 树里没有这个值
            u = ++tot; // 新建节点
            val[u] = k;
            tr[v][r] = u;
            fa[u] = v;
            cnt[u] = 1;
            pushup(u), pushup(v);
            splay(u); // 飞起来！
            return;
        }
    }
}

kth

查找第 $x$ 小的元素。

Val kth(int x) {
    // 需要保证第 x 小的数存在
    int u = root;
    while (true) {
        if (tr[u][0] && x <= siz[tr[u][0]]) {
            u = tr[u][0];
        } else {
            x -= siz[tr[u][0]] + cnt[u];
            if (x <= 0) {
                splay(u); // 飞起来！
                return val[u];
            }
            u = tr[u][1];
        }
    }
    return 114514;
}

rnk

查询元素 $k$ 的排名。注意：需要保证 $k$ 存在。

不存在的情况下，需要先 ins，查完之后 del。（当然我们现在还没有实现 del，因为 del 基于 rnk_）

int rnk_(Val k) {
    // 需要保证 k 存在
    int u = root, ans = 1;
    while (true) {
        if (k < val[u])
            u = tr[u][0];
        else {
            ans += siz[tr[u][0]];
            if (k == val[u]) {
                splay(u); // 飞起来！
                return ans;
            }
            ans += cnt[u];
            u = tr[u][1];
        }
    }
    return 114514;
}
int rnk(Val k) {
    ins(k);
    int ans = rnk_(k);
    del(k);
    return ans;
}

辅助操作：根的 pre / nxt

注意到这两个函数是没有输入的，所以不是我们想要的那个 pre / nxt。

这两个函数返回根节点的 pre / nxt 节点。

int pre() {
    int u = tr[root][0];
    while (tr[u][1])
        u = tr[u][1];
    splay(u); // 飞起来！
    return u;
}
int nxt() {
    int u = tr[root][1];
    while (tr[u][0])
        u = tr[u][0];
    splay(u); // 飞起来！
    return u;
}

有了这两个辅助操作之后，借助 ins 之后我们的值会被 splay 到顶的特性，我们希望的两个查询其实也很简单：

Val pre(Val k) { // 操作：查询前驱
    ins(k);
    Val ans = val[pre()];
    del(k);
    return ans;
}
Val nxt(Val k) { // 操作：查询后继
    ins(k);
    Val ans = val[nxt()];
    del(k);
    return ans;
}

del

先看代码：

void clear(int u) {
    fa[u] = siz[u] = tr[u][0] = tr[u][1] = cnt[u] = 0;
    val[u] = 0;
}
void del(Val k) {
    rnk_(k); // 把 k 所在的点 splay 上来
    if (cnt[root] > 1) { // 这个点的 cnt > 1，直接在 cnt 上减
        cnt[root]--;
        pushup(root);
    } else if (!tr[root][0] && !tr[root][1]) { // 整棵树删没了
        clear(root);
        root = 0;
    } else if (!tr[root][0]) { // 没左儿子，右儿子上位
        int u = root;
        root = tr[u][1];
        fa[root] = 0;
        clear(u);
    } else if (!tr[root][1]) { // 没右儿子，左儿子上位
        int u = root;
        root = tr[u][0];
        fa[root] = 0;
        clear(u);
    } else { // 左右儿子都有
        int u = root;
        root = pre();
        fa[tr[u][1]] = root;
        tr[root][1] = tr[u][1];
        clear(u);
        pushup(root);
    }
}

这里有一个特别骚的操作就是，调用 rnk_ 函数把这个元素给 splay 上来。

细说一下”左右儿子都有”这个部分：我们从左儿子的子树里取出一个最大的节点（即前面的辅助函数 pre），放到现在根节点的这个位置。

终于写完 Splay 的基本结构了。好累啊

平衡树的启发式合并

经过复杂的数学推导可以得到，Splay 和 Treap 的启发式合并是 $O(n \log n)$ 的，而不仅仅是预想中的 $O(n \log^2 n)$。

平衡树（Splay）维护序列 / 树

  • 序列，插入 / 区间查询 - 见 “火星人” 一题。
  • 树 DFS 序，子树查询 - 见 “Gty的游戏” 一题。

平衡树 例题

P4036 [JSOI2008] 火星人【强制在线】(Normal)

维护一个字符串，多次询问两个后缀的 LCP，这个字符串还带修改和插入。【强制在线】 操作次数 $\le 1.5 \times 10^5$，字符串长度始终满足 $\le 10^5$。

P.S. 这个题有离线时光倒流线段树的做法。

看到后缀 LCP（后缀的前缀是区间）不难想到二分 Hash。又有修改，想到 类似这样的题目，这个题目可以使用 树状数组 / 线段树 来完成。

但是现在这个题还有插入，那就只能 Splay 了。当然块状链表也是可以的，但是我们暂时只考虑 polylog；当然无旋 Treap 也是可以的，但是我们暂时只考虑 Splay 做法。

Splay 维护序列的核心在于，Splay 的中序遍历要保持是原序列。

首先是插入操作：在 $x$ 和 $x+1$ 这两个 index 之间插入一个元素，我们可以先把 $x$ splay 到顶，然后把 $x+1$ splay 到 $x$ 的儿子。此时 $x+1$ 必没有左儿子，我们就可以把新的点放在这里。

然后是区间查询 Hash 值：把 $l-1$ splay 到顶，把 $r+1$ splay 到 $l-1$ 的儿子，此时 $r+1$ 的左子树就是全部的 $[l,r]$，也就是说我们需要查询这棵树的中序遍历 Hash 值，像线段树一样在 pushup 的时候一起维护就行了。

注意到如果我们的查询是 $[1,n]$，则会访问到 $0$ 和 $n+1$，我们额外把这两个节点添上去就行了，即初始的时候就放好这两个节点，甚至省去了特判空树的代码。

单点修改不用多说了吧，$x$ splay 到顶直接改就行了

总时间复杂度 $O(n \log^2 n)$。

void insert(int x, Val k) {
    int u = kth(x), v = kth(x+1);
    splay(u);
    splay(v, u);
    int w = newNode();
    tr[v][0] = w;
    fa[w] = v;
    val[w] = k;
    splay(w);
}
void assign(int x, Val k) {
    int u = kth(x);
    splay(u);
    val[u] = k;
    pushup(u);
}
ull query_hash(int l, int r) {
    int u = kth(l-1), v = kth(r+1);
    splay(u);
    splay(v, u);
    return hsh[tr[v][0]];
}

课后作业 1 - BZOJ3729 Gty的游戏 (Hard)

给定一颗树，初始 $n$ 个结点，$1$ 为根节点。每个结点上有一定的石子数。 现在你需要在线支持三种操作：

  1. 询问以 $x$ 为根的子树中进行组合游戏，双方轮流操作，每次操作可以将一个结点（在子树内且不为 $x$）的不超过 $L$ 个至少 $1$ 个石子移至其父亲结点。问这个游戏先手是否必胜？
  2. 修改一个结点的石子数。
  3. 新建一个结点石子数为 $x$，其父亲设为 $y$（保证 $y$ 已经建立） $n \le 10^5$。

可以在 Hydro 提交。

首先这个博弈论和其他部分看起来格格不入的，分析一下。

博弈论部分分析

以下结论 0、结论 1 和结论 2 都应该是熟知的。

  • 结论 0：Nim 游戏的必胜条件是 $\bigoplus\limits_{i=1}^n a_i \ne 0$。
  • 结论 1：Nim 游戏（一次最多拿 $L$ 个）的必胜条件是 $\bigoplus\limits_{i=1}^n (a_i \bmod (L+1)) \ne 0$。
    • 证明：一方拿了 $x$ 个时，另一方可以在同一堆拿 $L+1 - x$ 个，变到一个 $\bmod (L+1)$ 下相同的局面。也就是说我们在 $\bmod (L+1)$ 下玩 Nim 游戏即可。
  • 结论 2：阶梯 Nim 游戏的必胜条件是 $\bigoplus\limits_{i \text{ is odd}} a_i \ne 0$。
    • 证明：首先如果一方动了 $2i$ 处的石子，另一方就可以把这些石子直接送去 $2i-2$，最终到 $0$。也就是说偶数处都可以看作 $0$ 即终点。那么动奇数处的石子就相当于直接送进终点，也就是我们对所有奇数处的石子玩 Nim 游戏就行了。
  • 结论 3：树上阶梯博弈的必胜条件是 $\bigoplus\limits_{dep_i \text{ is odd}} a_i \ne 0$。
    • 证明：结论 2 的直接推论。
  • 结论 4：树上阶梯博弈（一次最多拿 $L$ 个）的必胜条件是 $\bigoplus\limits_{dep_i \text{ is odd}} (a_i \bmod (L+1)) \ne 0$。
    • 证明：结论 1 和结论 3 的直接推论。

所以我们把所有 $a_i$ 对于 $L+1$ 取模就行了，然后就不管 $L$ 了。然后我们需要维护同奇偶深度节点的异或和。

博弈论部分转化完毕。

Splay 维护 DFS 序

子树询问，我们考虑把树拍成 DFS 序。在树上添加叶子就相当于在 DFS 序上插入，因此我们想到 Splay。

这题看起来似乎做完了，但是我们意识到做子树查询正常来说是需要维护子树大小的，此处不好做。

（以下防歧义，原树的节点用 $u,v$ 等字母，Splay 的节点用 $\alpha,\beta$ 等字母。）

（但是在代码中这两者可以混用。$u \to dfn_u \to \alpha$ 两层映射，我们可以直接让后面那层映射射回去来简化代码）

Splay 维护 DFS 序的经典 Trick：维护每个点在原树上的深度，对于节点 $u$ 找到 $dfn_u$ 之后的第一个满足 $dep_v \le dep_u$ 的节点 $v$，$[dfn_u, dfn_v)$ 就是以 $u$ 为根的子树占据的 $dfn$。

这个具体实现是，在 Splay 上维护 $\alpha$ 子树的节点中在原树上深度最小的那个节点的深度，不妨记为 $mn_\alpha$。我们从把 $dfn_u$ 对应的节点 $\alpha$ splay 到根，然后从 $\alpha$ 的右儿子开始找，通过维护的 $mn$ 定位到要找的节点 $\beta$，然后按照前面套路做就行了。把 $\text{pre}(\alpha)$ splay 到根，然后把 $\beta$ splay 到根的右儿子，取 $\beta$ 的左子树即可。

每次查询完 $\beta$ 之后，$\beta$ 都会紧接着在后面的操作被 splay 上去，所以复杂度应该是对的。

信息维护有点像 ABC403G 这个题。

P4309 [TJOI2013] 最长上升子序列【强制在线】(Easy)

共 $n$ 次操作，第 $i$ 次操作在第 $x_i$ 个数后插入数字 $i$ 并询问当前最长上升子序列。【强制在线】 $n \le 10^5$。

\[f_i = \max\limits_{j<i \text{ and } a_j < a_i} f_j + 1\]

注意到每次插入的数是递增的，也就意味着包含这个数的 LIS 一定以这个数结尾。也就是对于这个特定的 $i$，有：

\[f_i = \max\limits_{j<i} f_j + 1\]

也就是说，我们要知道这个数的 $f$ 只需要查询前缀的 $f$ 最大值即可。

插入 + 前缀查询，Splay 秒了。

P4197 Peaks (Easy)

类似题目：P3359 改造异或树

一个无向图，有边权和点权。若干个询问形如询问从点 $x$ 出发只能走边权不超过 $y$ 的边，走到所有点点权第 $k$ 大是多少。 $n \le 10^5$、$0 \le m,q \le 5 \times 10^5$、值域 $10^9$。

最简单的一道题。

把所有询问离线按 $y$ 排序，转化为加边。每个连通块维护一个带 kth 功能的 set（pbds 可以实现），启发式合并做到 2log，如果不用 pbds 而是用 Splay 或 Treap 可以做到 1log。

和题解区的线段树合并+线段树二分属于同一类型的做法。

跳表 (Skip List)

小常数数据结构，可以当平衡树用。优势在于对于单次操作，动态开点权值线段树 $O(\log V)$，跳表是期望 $O(\log n)$。

https://oi-wiki.org/ds/skiplist/

没啥用，不写了。

Tags:

You May Also Enjoy

TestPost

less than 1 minute read

Published:

这是一个 excerpt 嘿嘿

Cycle Space 与 Cut Space

4 minute read

Published:

讲解了无向图的 cycle space 和 cut space 的性质，并且尝试在有向图的情况进行类比。

图论 1

5 minute read

Published:

最短路、优化建图、差分约束、MST、Tarjan、2-SAT、Euler 路。

函数的极值

1 minute read

Published:

讲解了一些常用的函数极值处理手法。