「学习笔记」平衡树基础：Splay 和 Treap

点击查看目录

目录

• 「学习笔记」平衡树基础：Splay 和 Treap
  • 知识点
    • 平衡树概述
    • Splay
      • 旋转操作
      • Splay 操作
      • 插入 \(x\)
      • 查询排名为 \(k\) 的数
      • 查询 \(x\) 的排名
      • 查询 \(x\) 的前驱
      • 查询 \(x\) 的后继
      • 删除 \(x\)
      • 代码
    • 替罪羊树
    • Treap
    • FHQ_Treap
    • 树套树
    • 平衡树的区间操作
  • 例题
    • P3391 文艺平衡树
      • 思路
    • P4036 [JSOI2008]火星人
      • 思路
    • P4309 [TJOI2013]最长上升子序列
      • 思路
    • 星系探索
      • 思路
      • 代码

平衡树概述

二叉搜索树（BST）的简单定义：

• 根节点的左子树权值 \(<\) 根节点权值 \(<\) 根节点的右子树权值；
• 左子树和右子树均为二叉搜索树。

这样的数据结构可以维护一个集合的以下操作：

• 查找最小/最大值；
• 插入一个元素；
• 删除一个元素；
• 求元素的排名；
• 查找排名为 \(k\) 的元素。

该数据结构最优情况下单次查询仅需 \(\Theta(\log_2{n})\) 的时间复杂度，但通过构造输入可以使二叉搜索树退化为链，达到 \(\Theta(n)\) 的时间复杂度。

所以我们要让这棵二叉搜索树尽量平衡（深度接近 \(\log_2{n}\)）。

于是就诞生了平衡树。

Splay

旋转操作

可以发现左旋/右旋后树的形态发生变化，但仍然满足二叉搜索树的性质。

Splay 操作

Splay 的核心操作，即把一个点提到根。

分三种情况：

1. 爹就是根：直接转（\(\text{zig}\)）

2. 三点共线：先转爹，再转自己（\(\text{zig-zig}\)）

3. 三点不共线：直接转两下自己（\(\text{zig-zag}\)）：

为什么要这么转呢？因为直接单旋上去无法保证复杂度，随随便便就能卡掉，而双旋的时间复杂度可以用势能分析法进行分析。

插入 \(x\)

根据 BST 的性质找到一个地方插入新点，然后把它旋上去。

查询排名为 \(k\) 的数

假设当前到了点 \(p\)：

• \(k\) 小于 \(p\) 的左子树大小时往左走
• 否则令 \(k\) 减去 \(p\) 的左子树大小，然后：
  • 如果当前节点副本数大于等于 \(k\)，则当前节点的权值就是答案，然后把这个点旋上去。
  • 否则令 \(k\) 减去 \(p\) 的副本数。

查询 \(x\) 的排名

找到 \(x\) 提到根，左子树的大小加 \(1\) 就是答案。

查询 \(x\) 的前驱

把 \(x\) 提到根后，在左子树里一路往右走。

查询 \(x\) 的后继

把 \(x\) 提到根后，在右子树里一路往左走。

删除 \(x\)

最麻烦的一个。

首先我们把 \(x\) 提到根

• 此时如果 \(x\) 副本数大于 \(1\) 则直接让副本数减一。
• 否则看儿子数量：
  • 没儿子了：直接删。
  • 一个儿子：让儿子当根。
  • 两个儿子：首先把 \(x\) 的前驱提上来，因为刚才 \(x\) 是根并且最后一次旋转的时候不可能三点共线（不然就不是左子树的最大值了），所以此时根的右儿子是 \(x\)，且此时 \(x\) 无左儿子，所以直接把 \(x\) 的右儿子接到根的右儿子上就可以了。

代码

点击查看代码

const ll N = 2e5 + 10, INF = 1ll << 40;
namespace Splay {
    class TreePoint {
    public:
        ll val, cnt, sz;
        ll fa, son[2];
        inline void New (ll num) { val = num, cnt = sz = 1, fa = son[0] = son[1] = 0; return; }
        inline void Clear () { val = cnt = sz = fa = son[0] = son[1] = 0; return; }
    };

    class splay {
    public:
        TreePoint tr[N];
        ll tot = 0, rt = 0;

#define va(p) tr[p].val
#define cn(p) tr[p].cnt
#define sz(p) tr[p].sz
#define fa(p) tr[p].fa
#define so(p, lr) tr[p].son[lr]

        inline void PushUp (ll p) { sz (p) = sz (so (p, 0)) + sz (so (p, 1)) + cn (p); return; } // Update the size.
        inline bool Get (ll p) { return p == so (fa (p), 1); } // Left son(0) or right son(1)?
        inline ll NewPoint (ll num) { tr[++tot].New (num); return tot; } // Build a new Point.

        inline void Rotate (ll p) {
            ll q = fa (p), r = fa (q), sd = Get (p);
            so (q, sd) = so (p, sd ^ 1);
            if (so (p, sd ^ 1)) fa (so (p, sd ^ 1)) = q;
            so (p, sd ^ 1) = q, fa (q) = p, fa (p) = r;
            if (r) so (r, q == so (r, 1)) = p;
            PushUp (q), PushUp (p);
            return;
        } // Zig or zag.
        inline void Splay (ll p) {
            for (ll q = fa (p); q = fa (p), q; Rotate (p))
                if (fa (q)) Rotate (Get (p) == Get (q) ? q : p);
            rt = p;
            return;
        } // Splay's core operations!

        inline void Out () {
            _for (i, 1, tot) {
                printf ("%lld : val=%lld cnt=%lld sz=%lld fa=%lld  %lld %lld\n", i, va (i), cn (i), sz (i), fa (i), so (i, 0), so (i, 1));
            }
            puts ("");
            return;
        } // For debug.

        inline void Insert (ll x) {
            if (!rt) rt = NewPoint (x), PushUp (rt);
            else {
                ll p = rt;
                while (1) {
                    ll sd = (bool)(va (p) < x);
                    if (va (p) == x) {
                        ++cn (p);
                        PushUp (p), PushUp (fa (p));
                        break;
                    }
                    else if (so (p, sd)) p = so (p, sd);
                    else {
                        so (p, sd) = NewPoint (x);
                        fa (so (p, sd)) = p, p = so (p, sd);
                        PushUp (p), PushUp (fa (p));
                        break;
                    }
                }
                Splay (p);
            }
            return;
        } // Insert a number x.
        inline ll GetRank (ll x) {
            ll p = rt, cnt = 1;
            while (p) {
                if (va (p) <= x) {
                    cnt += sz (so (p, 0));
                    if (va (p) == x) break;
                    cnt += cn (p);
                    p = so (p, 1);
                }
                else p = so (p, 0);
            }
            Splay (p);
            return cnt;
        } // Get x's rank.
        inline ll GetKth (ll x) {
            ll p = rt;
            while (p) {
                if (sz (so (p, 0)) < x) {
                    x -= sz (so (p, 0));
                    if (cn (p) >= x) break;
                    x -= cn (p);
                    p = so (p, 1);
                }
                else p = so (p, 0);
            }
            Splay (p);
            return va (p);
        } // Get k-th number.
        inline ll RealPre () {
            ll p = so (rt, 0);
            if (p) {
                while (so (p, 1)) p = so (p, 1);
                Splay (p);
            }
            return p;
        }
        inline void Delete (ll x) {
            GetRank (x);
            ll sd = (bool)(so (rt, 1));
            if (cn (rt) > 1) --cn (rt), PushUp (rt);
            else if (!so (rt, 0) && !so (rt, 1)) tr[rt].Clear (), rt = 0;
            else if (so (rt, 0) && so (rt, 1)) {
                ll p = rt, q = RealPre ();
                fa (so (p, 1)) = q;
                so (q, 1) = so (p, 1);
                tr[p].Clear ();
                PushUp (rt);
            }
            else {
                ll q = so (rt, sd);
                tr[rt].Clear ();
                fa (rt = q) = 0;
            }
            return;
        } // Delete a number x.
        inline ll Pre (ll x) {
            Insert (x);
            ll ans = va (RealPre ());
            Delete (x);
            return ans;
        } // Get x's pre.
        inline ll Next (ll x) {
            Insert (x);
            ll p = so (rt, 1), ans = 0;
            if (p) {
                while (so (p, 0)) p = so (p, 0);
                Splay (p);
            }
            ans = va (rt);
            Delete (x);
            return ans;
        } // Get x's next.

#undef va
#undef cn
#undef sz
#undef fa
#undef so
    };
} 

替罪羊树

很暴力的一个东西。

定义一个平衡因子 \(\alpha\)（最好选 \(0.7\sim0.8\)），插入/删除一个节点的时候检查是否存在一个节点的子树的大小乘上 \(\alpha\) 小于左/右儿子树的大小，如果有则把这棵子树直接拍平重构。

其他操作和普通 BST 一样。

点击查看代码

namespace ScapeGoatTree {
    const ldb alpha = 0.75;
    const ll N = 1e5 + 10;
    class TreePoint {
    public:
        ll val, cnt, sz, cp, del;
        ll fa, son[2];
    };
    class SGT {
    private:
        ll tot = 0, rt = 0, dp[N], cd = 0;
        TreePoint tr[N];
        vec tmp, c;

#define va(p) tr[p].val
#define cn(p) tr[p].cnt
#define sz(p) tr[p].sz
#define de(p) tr[p].del
#define cp(p) tr[p].cp
#define fa(p) tr[p].fa
#define so(p, lr) tr[p].son[lr]

        inline ll NewP (ll num) {
            ll p = cd ? dp[cd--] : ++tot;
            va (p) = num;
            cn (p) = sz (p) = 1;
            cp (p) = fa (p) = so (p, 0) = so (p, 1) = de (p) = 0;
            return p;
        }
        inline void DelP (ll p) {
            va (p) = cn (p) = sz (p) = cp (p) = fa (p) = so (p, 0) = so (p, 1) = de (p) = 0;
            dp[++cd] = p;
            return;
        }
        inline void PushUp (ll p) {
            sz (p) = (de (p) ? 0 : cn (p)) + sz (so (p, 0)) + sz (so (p, 1));
            cp (p) = 1 + cp (so (p, 0)) + cp (so (p, 1));
            return;
        }

    public:
        inline void Clap (ll p) {
            if (so (p, 0)) Clap (so (p, 0));
            if (!de (p)) tmp.push_back (va (p)), c.push_back (cn (p));
            if (so (p, 1)) Clap (so (p, 1));
            DelP (p);
            return;
        }
        inline ll PullUp (ll l, ll r, ll fat) {
            if (l > r) return 0;
            bdmd;
            ll p = NewP (tmp[mid]);
            cn (p) = c[mid], fa (p) = fat;
            if (l < mid) so (p, 0) = PullUp (l, mid - 1, p);
            if (mid < r) so (p, 1) = PullUp (mid + 1, r, p);
            PushUp (p);
            return p;
        }
        inline void ReBuild (ll p) {
            ll q = fa (p);
            tmp.clear (), c.clear ();
            Clap (p);
            if (!q) rt = PullUp (0, tmp.size () - 1, q);
            else so (q, p == so (q, 1)) = PullUp (0, tmp.size () - 1, q);
            return;
        }

        inline bool Bad (ll p) {
            return cp (so (p, 0)) > cp (p) * alpha || cp (so (p, 1)) > cp (p) * alpha;
        }
        inline void Check (ll p) {
            ll q = 0;
            while (p) {
                if (Bad (p)) q = p;
                rt = p;
                PushUp (p);
                p = fa (p);
            }
            if (q) ReBuild (q);
            return;
        }

        inline void Insert (ll num) {
            ll p = rt;
            if (!rt) {
                rt = NewP (num);
                return;
            }
            while (1) {
                if (va (p) == num) {
                    ++cn (p);
                    if (de (p)) de (p) = 0;
                    Check (p);
                    return;
                }
                ll sd = num > va (p);
                if (so (p, sd)) p = so (p, sd);
                else {
                    so (p, sd) = NewP (num);
                    fa (so (p, sd)) = p;
                    Check (p);
                    return;
                }
            }
            return;
        }
        inline void Delete (ll num) {
            ll p = rt;
            while (p) {
                if (va (p) == num) {
                    --cn (p);
                    if (cn (p) < 1) {
                        cn (p) = 0;
                        de (p) = 1;
                    }
                    Check (p);
                    return;
                }
                ll sd = num > va (p);
                p = so (p, sd);
            }
            return;
        }
        inline ll GetRank (ll num) {
            ll p = rt, rk = 1;
            while (p) {
                if (va (p) > num) {
                    p = so (p, 0);
                    continue;
                }
                rk += sz (so (p, 0));
                if (num == va (p)) break;
                rk += cn (p);
                p = so (p, 1);
            }
            return rk;
        }
        inline ll GetKth (ll k) {
            ll p = rt;
            while (p) {
                if (sz (so (p, 0)) >= k) {
                    p = so (p, 0);
                    continue;
                }
                k -= sz (so (p, 0));
                if (k <= cn (p)) break;
                k -= cn (p);
                p = so (p, 1);
            }
            return va (p);
        }
        inline ll Pre (ll num) { return GetKth (GetRank (num) - 1); }
        inline ll Nxt (ll num) { return GetKth (GetRank (num + 1)); }

#undef va
#undef cn
#undef sz
#undef de
#undef cp
#undef fa
#undef so
    };
} 

Treap

每个节点还要存一个随机权值，使得整棵树不仅对于原权值来说是一棵 BST，对于随机权值来说还是一个堆，在随机状态下一棵 Treap 是比较 \(\log_2n\) 层的。当然不排除你脸太黑导致 Treap 退化成链的极小可能。

那么插入的时候，如果新节点不满足堆的性质了，需要往上旋转。删除的时候直接旋到叶子结点删掉，或者只剩一个儿子的时候直接让儿子代替自己。

其他操作和普通 BST 一样。

点击查看代码

namespace TREAP {
    class TreePoint {
    public:
        ll val, rk, sz, cnt;
        ll son[2];
        inline void NewP (ll x) { val = x, rk = rand (), cnt = sz = 1, son[0] = son[1] = 0;return; }
    };
    class Treap {
    public:
        TreePoint tr[N];
        ll tot = 0, rt = 0;

#define va(p) tr[p].val
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define cn(p) tr[p].cnt
#define so(p, lr) tr[p].son[lr]

        inline void PushUp (ll p) { sz (p) = cn (p) + sz (so (p, 0)) + sz (so (p, 1)); return; }
        inline ll NewP (ll num) { tr[++tot].NewP (num); return tot; }
        inline void DelP (ll p) { va (p) = rk (p) = sz (p) = cn (p) = so (p, 0) = so (p, 1) = 0;return; }

        inline void Rotate (ll& p, ll sd) {
            ll q = so (p, sd ^ 1);
            so (p, sd ^ 1) = so (q, sd);
            so (q, sd) = p, p = q;
            PushUp (so (q, sd)), PushUp (q);
            return;
        }

        void Insert (ll& p, ll x) {
            if (!p) {
                p = NewP (x);
                return;
            }
            if (va (p) == x) ++cn (p);
            else {
                bool sd = (va (p) < x);
                Insert (so (p, sd), x);
                if (rk (so (p, sd)) > rk (p)) Rotate (p, sd ^ 1);
            }
            PushUp (p);
            return;
        }
        void Delete (ll& p, ll x) {
            if (!p) return;
            if (va (p) == x) {
                if (cn (p) == 1) {
                    if (!so (p, 0) && !so (p, 1)) DelP (p), p = 0;
                    else if (!so (p, 0) || !so (p, 1)) p = so (p, 0) + so (p, 1);
                    else {
                        ll sd = (rk (so (p, 1)) < rk (so (p, 0)));
                        Rotate (p, sd), Delete (so (p, sd), x);
                    }
                }
                else --cn (p);
            }
            else Delete (so (p, (x > va (p))), x);
            PushUp (p);
            return;
        }
        ll GetRank (ll p, ll x) {
            if (!p) return 1;
            if (va (p) == x) return 1 + sz (so (p, 0));
            if (va (p) < x) return GetRank (so (p, 1), x) + sz (so (p, 0)) + cn (p);
            return GetRank (so (p, 0), x);
        }
        ll GetKth (ll p, ll x) {
            if (!p) return 0;
            if (x <= sz (so (p, 0))) return GetKth (so (p, 0), x);
            x -= sz (so (p, 0));
            if (x <= cn (p)) return va (p);
            x -= cn (p);
            return GetKth (so (p, 1), x);
        }
        ll Pre (ll x) { return GetKth (rt, GetRank (rt, x) - 1); }
        ll Next (ll x) { return GetKth (rt, GetRank (rt, x + 1)); }

#undef va
#undef rk
#undef sz
#undef cn
#undef so
    };
} 

FHQ_Treap

FHQ_Treap 依旧满足 Treap 的性质，但是操作方式很神奇！

FHQ_Treap 也被称为无旋 Treap，因为它的所有操作都没有恶心的旋转，只有分裂和合并两个基础操作！

分裂有两种方法：按权值裂和按排名裂。一般来说，只当平衡树的时候通常按权值裂，维护序列的时候按排名裂。具体怎么裂见代码和例题。

合并的时候要保证第一棵树的所有权值都比第二棵树小，注意合的过程中要保证 Treap 的性质。

为了方便写我没有写副本数。

然后就是六个操作了：

• 插入

  按 \(x\) 裂成 \(a,b\) 两棵树，然后按 \(a,x,b\) 的顺序合起来

• 删除

  这绝对是删除操作最简单的平衡树了！先按 \(x\) 裂成 \(a,b\) 两棵树，再把 \(a\) 按 \(x-1\) 裂成 \(a,c\) 两棵树，此时

• 查询排名为 \(k\) 的数

  和普通 BST 一样。

• 查询 \(x\) 的排名

  按 \(x-1\) 裂成 \(a,b\) 两棵树，\(a\) 的大小加一就是答案

• 查询 \(x\) 的前驱

  按 \(x-1\) 裂成 \(a,b\) 两棵树，\(a\) 里的最大值

• 查询 \(x\) 的后继

  按 \(x-1\) 裂成 \(a,b\) 两棵树，\(b\) 里的最小值

点击查看代码

namespace FHQ_TREAP {
    class TreeNode {
    public:
        ll val, rk, sz, son[2];
        inline void Add (ll num) { val = num, rk = rand (), sz = 1, son[0] = son[1] = 0; return; }
    };
    class FHQTreap {
    private:
        TreeNode tr[N];
        ll tot = 0, rt = 0, a, b, c;

#define va(p) tr[p].val
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define so(p, lr) tr[p].son[lr]

        inline ll NewP (ll num) { tr[++tot].Add (num); return tot; }
        inline void PushUp (ll p) { sz (p) = 1 + sz (so (p, 0)) + sz (so (p, 1)); return; }

        void Split (ll p, ll x, ll& l, ll& r) {
            if (!p) l = r = 0;
            else {
                if (va (p) <= x) l = p, Split (so (p, 1), x, so (p, 1), r);
                else r = p, Split (so (p, 0), x, l, so (p, 0));
                PushUp (p);
            }
            return;
        }
        inline ll Merge (ll l, ll r) {
            if (!l || !r) return l + r;
            if (rk (l) < rk (r)) {
                so (l, 1) = Merge (so (l, 1), r);
                PushUp (l);
                return l;
            }
            else {
                so (r, 0) = Merge (l, so (r, 0));
                PushUp (r);
                return r;
            }
        }

    public:
        inline void Insert (ll x) {
            Split (rt, x, a, b);
            rt = Merge (Merge (a, NewP (x)), b);
            return;
        }
        inline void Delete (ll x) {
            Split (rt, x, a, b);
            Split (a, x - 1, a, c);
            rt = Merge (Merge (a, Merge (so (c, 0), so (c, 1))), b);
            return;
        }
        inline ll GetRank (ll x) {
            Split (rt, x - 1, a, b);
            ll ans = sz (a) + 1;
            rt = Merge (a, b);
            return ans;
        }
        inline ll GetKth (ll x) {
            ll p = rt;
            while (p) {
                if (x <= sz (so (p, 0))) p = so (p, 0);
                else {
                    x -= sz (so (p, 0)) + 1;
                    if (!x) break;
                    p = so (p, 1);
                }
            }
            return va (p);
        }
        inline ll Pre (ll x) {
            Split (rt, x - 1, a, b);
            ll p = a;
            while (so (p, 1)) p = so (p, 1);
            rt = Merge (a, b);
            return va (p);
        }
        inline ll Next (ll x) {
            Split (rt, x, a, b);
            ll p = b;
            while (so (p, 0)) p = so (p, 0);
            rt = Merge (a, b);
            return va (p);
        }

#undef va
#undef rk
#undef sz
#undef so
    };
} 

树套树

用于维护单点修改和区间第 \(k\) 大，排名，前驱和后继的查询。

首先建立一棵线段树，每个节点单建一棵平衡树维护这个区间（线段树的每一层有 \(n\) 个节点，一共 \(\log_2n\) 层，因此只有 \(n\log_2n\) 个节点，不会 TLE/MLE）。

然后是如何维护五个操作：

• 单点修改：所有包含这个点的平衡树删除原来这个点的数，再插入新数。
• \(x\) 的区间排名：将在这个区间内的平衡树的 \(x\) 加起来。
• \(x\) 的区间第 \(k\) 大：使用二分，找到一个数的区间排名是 \(k\)。
• \(x\) 的区间前驱：这个区间内的所有平衡树中 \(x\) 的前驱最大值。
• \(x\) 的区间后继：这个区间内的所有平衡树中 \(x\) 的后继最小值。

点击查看代码

const ll N = 1e5 + 10, inf = 2147483647;

namespace FHQ_TREAP {
    class TreeNode {
    public:
        ll val, rk, sz, son[2];
        inline void Add (ll num) noexcept { val = num, rk = rand (), sz = 1, son[0] = son[1] = 0; return; }
    } tr[N << 4];
    ll tot = 0, len = 0, free[N << 4];

#define va(p) tr[p].val
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define so(p, lr) tr[p].son[lr]

    class FHQTreap {
    private:
        ll rt = 0, a, b, c;

        inline void PushUp (ll p) noexcept { sz (p) = 1 + sz (so (p, 0)) + sz (so (p, 1)); }
        inline ll NewP (ll num) noexcept {
            ll p = len ? free[len--] : ++tot;
            tr[p].Add (num);
            return p;
        }
        inline void DelP (ll p) noexcept {
            va (p) = rk (p) = sz (p) = so (p, 0) = so (p, 1) = 0;
            free[++len] = p;
            return;
        }

        inline void Split (ll p, ll x, ll& l, ll& r) noexcept {
            if (!p) l = r = 0;
            else {
                if (va (p) <= x) l = p, Split (so (p, 1), x, so (p, 1), r);
                else r = p, Split (so (p, 0), x, l, so (p, 0));
                PushUp (p);
            }
            return;
        }
        inline ll Merge (ll l, ll r) noexcept {
            if (!l || !r) return l + r;
            if (rk (l) > rk (r)) {
                so (l, 1) = Merge (so (l, 1), r);
                PushUp (l);
                return l;
            }
            else {
                so (r, 0) = Merge (l, so (r, 0));
                PushUp (r);
                return r;
            }
        }

    public:
        inline void Insert (ll x) noexcept {
            Split (rt, x, a, b);
            rt = Merge (Merge (a, NewP (x)), b);
            return;
        }
        inline void Delete (ll x) noexcept {
            Split (rt, x, a, b);
            Split (a, x - 1, a, c);
            rt = Merge (Merge (a, Merge (so (c, 0), so (c, 1))), b);
            DelP (c);
            return;
        }
        inline ll GetRank (ll x) noexcept {
            Split (rt, x - 1, a, b);
            ll ans = sz (a);
            rt = Merge (a, b);
            return ans;
        }
        inline ll Pre (ll x) noexcept {
            Split (rt, x - 1, a, b);
            ll p = a;
            while (so (p, 1)) p = so (p, 1);
            rt = Merge (a, b);
            return va (p);
        }
        inline ll Next (ll x) noexcept {
            Split (rt, x, a, b);
            ll p = b;
            while (so (p, 0)) p = so (p, 0);
            rt = Merge (a, b);
            return va (p);
        }
    };

#undef va
#undef rk
#undef sz
#undef so
}

namespace SEGMENT_TREE {
    class SegmentTree {
    private:
        FHQ_TREAP::FHQTreap tr[N << 2];

#define ls(p) p << 1, l, mid
#define rs(p) p << 1 | 1, mid + 1, r

    public:
        inline void Build (ll p, ll l, ll r, ll* a) noexcept {
            if (l != r) {
                ll mid = md;
                Build (ls (p), a);
                Build (rs (p), a);
            }
            tr[p].Insert (inf), tr[p].Insert (-inf);
            _for (i, l, r) tr[p].Insert (a[i]);
            return;
        }
        inline void Update (ll p, ll l, ll r, ll x, ll y, ll z) noexcept {
            if (r < x || x < l) return;
            if (l != r) {
                ll mid = md;
                Update (ls (p), x, y, z);
                Update (rs (p), x, y, z);
            }
            tr[p].Delete (z), tr[p].Insert (y);
        }
        inline ll QueryRank (ll p, ll l, ll r, ll le, ll ri, ll x) noexcept {
            if (ri < l || r < le) return 0;
            ll mid = md;
            if (le <= l && r <= ri) return tr[p].GetRank (x) - 1;
            else return QueryRank (ls (p), le, ri, x) + QueryRank (rs (p), le, ri, x);
        }
        inline ll QueryKth (ll le, ll ri, ll x, ll n, ll mx) noexcept {
            ll l = 0, r = mx, ans = 0;
            while (l <= r) {
                ll mid = md;
                if (QueryRank (1, 1, n, le, ri, mid) + 1 <= x) ans = mid, l = mid + 1;
                else r = mid - 1;
            }
            return ans;
        }
        inline ll QueryPre (ll p, ll l, ll r, ll le, ll ri, ll x) noexcept {
            if (ri < l || r < le) return -inf;
            ll mid = md;
            if (le <= l && r <= ri) return tr[p].Pre (x);
            else return std::max (QueryPre (ls (p), le, ri, x), QueryPre (rs (p), le, ri, x));
        }
        inline ll QueryNext (ll p, ll l, ll r, ll le, ll ri, ll x) noexcept {
            if (ri < l || r < le) return inf;
            ll mid = md;
            if (le <= l && r <= ri) return tr[p].Next (x);
            else return std::min (QueryNext (ls (p), le, ri, x), QueryNext (rs (p), le, ri, x));
        }
    };
} 

平衡树的区间操作

平衡树不是只能平衡树，也可以进行区间操作。

用平衡树中序遍历顺序不变的性质，维护序列中每个数的前后位置（即把按数值排序变为按下标排序）。

操作时，把需要操作/查询的区间放在一颗子树上再直接对子树进行操作/查询。

如果操作对子树的所有点生效，应该给子树打个标记，旋转/分裂/合并的时候随手下传标记。

具体的

使用 Splay：通过对 \(l-1\) 和 \(r+1\) 提根使得区间 \([l, r]\) 在一颗子树上，然后对这棵子树进行操作。

使用 FHQ-Treap：把区间 \([l, r]\) 裂出来，然后对这棵子树进行操作，再合并回去。

平衡树还支持插入/删除一个点，所以维护序列的时候还可以在任意位置加入/删除一个数。

另外，FHQ-Treap 裂开合并的神奇操作还支持对一个区间进行移动。

P3391 文艺平衡树

思路

对需要操作的区间打个翻转标记，同时交换其左右儿子。

P4036 [JSOI2008]火星人

思路

维护一棵子树的字符串的哈希值，然后就是裸的区间操作了。

P4309 [TJOI2013]最长上升子序列

思路

不难发现每次插入的数都会比之前插入的数都大，因此插完之后最长上升子序列的长度不会变化。

那么每个节点维护一个子树最长上升子序列的长度的最大值，插入时选一个前面的最长的最长上升子序列接上。

星系探索

思路

把这棵树转换成 dfs 序序列，然后对于三个操作：

• 求 \(u\) 到根的权值和：求 \(u\) 在 dfs 序序列上的前缀和。
• 改变 \(u\) 的父亲：移动 \(u\) 子树的 dfs 序序列代表的区间的位置。
• 给 \(u\) 子树加一个定值：把 \(u\) 子树的 dfs 序序列代表的区间裂出来，打个标记再合并回去。

代码

点击查看代码

const ll N = 1e6+ 10;

namespace FHQ_TREAP {
    class TreeNode {
    public:
        ll val, pn, rk, sz, so[2], ta, sum, sp, fa;
        inline void Add (ll num, ll tmp) { sum = val = num * tmp, sp = pn = tmp, rk = rand (), sz = 1, so[0] = so[1] = 0; return; }
    };
    class FHQTreap {
    private:
        TreeNode tr[N];
        ll tot = 0, rt = 0, a, b, c;

#define va(p) tr[p].val
#define ta(p) tr[p].ta
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define pn(p) tr[p].pn
#define su(p) tr[p].sum
#define sp(p) tr[p].sp
#define fa(p) tr[p].fa
#define so(p, lr) tr[p].so[lr]

        inline ll NewP (ll num, ll pn) { tr[++tot].Add (num, pn); return tot; }
        inline void PushUp (ll p) {
            sz (p) = 1 + sz (so (p, 0)) + sz (so (p, 1));
            su (p) = va (p) + su (so (p, 0)) + su (so (p, 1));
            sp (p) = pn (p) + sp (so (p, 0)) + sp (so (p, 1));
            fa (so (p, 0)) = fa (so (p, 1)) = p;
            return;
        }
        inline void Tag (ll p, ll num) {
            ta (p) += num;
            va (p) += num * pn (p);
            su (p) += num * sp (p);
            return;
        }
        inline void PushDown (ll p) {
            if (!ta (p)) return;
            if (so (p, 0)) Tag (so (p, 0), ta (p));
            if (so (p, 1)) Tag (so (p, 1), ta (p));
            fa (so (p, 0)) = fa (so (p, 1)) = p;
            ta (p) = 0;
            return;
        }

        inline void Split (ll p, ll x, ll& l, ll& r) {
            if (!p) l = r = 0;
            else {
                PushDown (p);
                if (sz (so (p, 0)) < x) l = p, Split (so (p, 1), x - sz (so (p, 0)) - 1, so (p, 1), r);
                else r = p, Split (so (p, 0), x, l, so (p, 0));
                PushUp (p);
            }
            return;
        }
        inline ll Merge (ll l, ll r) {
            PushDown (l), PushDown (r);
            if (!l || !r) return l + r;
            if (rk (l) > rk (r)) {
                so (l, 1) = Merge (so (l, 1), r);
                PushUp (l);
                return l;
            }
            else {
                so (r, 0) = Merge (l, so (r, 0));
                PushUp (r);
                return r;
            }
        }
        inline ll GetRank (ll x) {
            ll cnt = sz (so (x, 0)) + 1;
            for (ll p = x; fa (p); p = fa (p))
                if (so (fa (p), 1) == p) cnt += sz (so (fa (p), 0)) + 1;
            return cnt;
        }

    public:
        inline void Insert (ll x, ll p) {
            rt = Merge (rt, NewP (x, p));
            return;
        }
        inline void Modify (ll l, ll r, ll x) {
            l = GetRank (l), r = GetRank (r);
            Split (rt, r, a, b);
            Split (a, l - 1, a, c);
            Tag (c, x);
            rt = Merge (Merge (a, c), b);
            return;
        }
        inline void Move (ll l, ll r, ll x) {
            l = GetRank (l), r = GetRank (r), x = GetRank (x);
            if (x > r) x -= r - l + 1;
            Split (rt, r, a, b);
            Split (a, l - 1, a, c);
            a = Merge (a, b);
            Split (a, x, a, b);
            rt = Merge (Merge (a, c), b);
            return;
        }
        inline ll Query (ll x) {
            x = GetRank (x);
            Split (rt, x, a, b);
            ll ans = su (a);
            rt = Merge (a, b);
            return ans;
        }

#undef va
#undef ta
#undef rk
#undef sz
#undef pn
#undef su
#undef sp
#undef fa
#undef so
    };
}

namespace SOLVE {
    FHQ_TREAP::FHQTreap tr;
    ll n, m, fa[N], w[N], cnt;
    ll dfn[N], sec[N][2];
    std::vector<ll> tu[N];
    inline ll rnt () {
        ll x = 0, w = 1; char c = getchar ();
        while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
        while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
        return x * w;
    }
    inline char rch () {
        char c = getchar ();
        while (c < 'A' || 'Z' < c) c = getchar ();
        return c;
    }
    inline void Dfs (ll x) {
        dfn[sec[x][0] = ++cnt] = x;
        tr.Insert (w[x], 1);
        far (i, tu[x]) Dfs (i);
        sec[x][1] = ++cnt;
        tr.Insert (w[x], -1);
        return;
    }
    inline void In () {
        n = rnt ();
        _for (i, 2, n) {
            fa[i] = rnt ();
            tu[fa[i]].push_back (i);
        }
        _for (i, 1, n) w[i] = rnt ();
        m = rnt ();
        Dfs (1);
        return;
    }
    inline void Out () {
        while (m--) {
            char opt = rch ();
            if (opt == 'Q') {
                ll d = rnt ();
                printf ("%lld\n", tr.Query (sec[d][0]));
            }
            else if (opt == 'C') {
                ll x = rnt (), y = rnt ();
                tr.Move (sec[x][0], sec[x][1], sec[y][0]);
            }
            else {
                ll x = rnt (), y = rnt ();
                tr.Modify (sec[x][0], sec[x][1], y);
            }
        }
        return;
    }
} 

\[\Huge\mathfrak{The End}
\]