「SuperMemo」 超级备忘录

GitHub跳转原题关系图返回列表

序列会被翻转、轮换、插入、删除，按位置组织的静态结构全部失效；用平衡树按中序维护显式序列，两次 splay 切出区间子树后打整树加与翻转懒标记，轮换化为三次翻转，每个操作均摊 O(log n)。

OJ: roj

题目 ID: 3129

难度:省选/NOI-

标签:平衡树Splay懒标记区间操作python

创建: 2026-10-01 18:41

更新: 2026-10-10 11:30

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结
  4. 图示解析

形式化题目

给定一个长度为 nn 的数列 A1,A2,…,AnA_1, A_2, \ldots, A_n，依次处理 MM 条操作：

  • ADD x y D：Ax,…,AyA_x, \ldots, A_y 每个数加 DD；
  • REVERSE x y：翻转 Ax,…,AyA_x, \ldots, A_y；
  • REVOLVE x y T：把 Ax,…,AyA_x, \ldots, A_y 右轮换 TT 次（每轮把区间最后一个数移到区间最前）；
  • INSERT x P：在 AxA_x 后面插入一个数 PP（序列长度加一）；
  • DELETE x：删除 AxA_x（序列长度减一）；
  • MIN x y：输出 Ax,…,AyA_x, \ldots, A_y 中的最小值。

n,M⩽105n, M \leqslant 10^5。所有下标都指当前序列中的位置；每个 MIN 输出一行答案。

正解

思路

先用数组朴素模拟找找瓶颈：ADD 和 MIN 用线段树或差分都能到 O(log⁡n)O(\log n)，但 REVERSE、REVOLVE 要把区间逐个元素翻过来，INSERT、DELETE 要搬动后半段所有元素，单次最坏 O(n)O(n)，总代价 O(nM)=1010O(nM) = 10^{10}，必然超时。瓶颈的本质是：序列的元素位置一直在变，任何"按下标组织"的静态结构都无法应付翻转和插删。

所以要换一种组织方式：用平衡树（Splay）保存序列，但不按值、而按中序位置理解它——把树中序遍历一遍，得到的恰好就是当前序列。这样：

  • "序列的一段 [x,y][x, y]“对应"树中连续一段中序”，而树中连续一段中序恰好组成一颗完整子树；
  • 只要能把这颗子树完整地"切"出来，区间操作就变成对单个节点的懒标记。

区间切分：在序列两端各加一个值为 +∞+\infty 的哨兵，树的中序固定为 [左哨兵, A₁, …, Aₙ, 右哨兵]，这样 AyA_y 的后继永远存在。把 Ax−1A_{x-1}（x=1x=1 时即左哨兵）转到根，再把树中第 y+2y+2 个元素（即 AyA_y 的后继）转到根的孩子，此时后继的左子树恰好就是整个区间，可用子树大小验证。两次 splay，均摊 O(log⁡n)O(\log n)。

切出子树后，六种操作全部落在子树根这一个节点上：

操作 在切出的子树根上做什么
ADD x y D 打 add 懒标记，同步修正该点的 val/mn
REVERSE x y 打 rev 懒标记（下传时交换左右子树）
REVOLVE x y T 转化为三次 REVERSE（见下）
INSERT x P 定位 AxA_x 与其后继，两针之间接一个新叶子
DELETE x 定位 Ax−1A_{x-1} 与 AxA_x 的后继，摘掉中间那颗单节点子树
MIN x y 直接读子树根维护的子树最小值 mn

轮换化翻转：设区间为 A BA\,B（AA 是前 len−tlen-t 个，BB 是后 tt 个），右轮换 tt 次的目标是 B AB\,A。由 (ArBr)r=B A(A^r B^r)^r = B\,A（XrX^r 表示把 XX 翻转），依次"翻 AA、翻 BB、整段再翻"即可，完全复用 REVERSE 的懒标记。TT 先对区间长度取模，为 00 直接跳过。

正确性要点：懒标记可以一直"趴"在子树根上不下传——因为整树加 DD 时子树最小值恰好也加 DD，整树翻转时子树最小值根本不变，所以 mn 在打标记处就能算对；只有真正要进入子树（kth、切分）时才沿路径下传，均摊不改变复杂度。

用样例演示 ADD 2 4 1 的切树过程（树只画中序骨架，∞\infty 是哨兵）：

flowchart TB
    subgraph G0["初始：中序 = ∞ 1 2 3 4 5 ∞"]
        R0["∞（根）"] --- A0["1 2 3 4 5 ∞"]
    end
    subgraph G1["第 1 次 splay：A₁=1 转到根"]
        R1["1（根）"] --- L1["∞"] --- C1["2 3 4 5 ∞"]
    end
    subgraph G2["第 2 次 splay：A₄ 的后继 5 转到 1 的孩子"]
        R2["1（根）"] --- C2["2 3 4（完整子树）"] --- S2["5"] --- T2["∞"]
    end
    subgraph G3["对子树根打 add=+1，MIN 4 5 再切一次读 mn"]
        R3["1"] --- C3["3 4 5<br/>add=+1，mn=3"] --- S3["5"] --- T3["∞"]
    end
    G0 --> G1 --> G2 --> G3

观察重点：第 2 步之后"2 3 4"成为一颗父子关系完整的子树，此后加标记只碰它的根，翻转也只碰它的根，区间外的任何节点都不再被触及——这就是所有操作 O(log⁡n)O(\log n) 的来源。

再看 REVOLVE 2 4 2 的三次翻转（区间是 3 4 5，t=2t = 2）：

步骤 区间内容 动作
初始 3 4 5 目标：尾部 2 个移到前面，即 4 5 3
翻前 len−t=1len-t=1 个 3 → 3 ArA^r，单元素不变
翻后 t=2t=2 个 4 5 → 5 4 BrB^r
整段翻转 3 5 4 → 4 5 3 (ArBr)r=BA(A^r B^r)^r = B A ✓

三次懒标记全部打在同一颗子树的根上，push 时一次性生效。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 文艺平衡树扩展（ADD / REVERSE / REVOLVE / INSERT / DELETE / MIN）：Splay 维护区间。
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>

typedef long long ll;

const ll INF = 1000000000000000000LL;

struct Node {
    int ch[2];   // 左 / 右孩子
    int fa;      // 父亲
    ll val;      // 节点自身的值
    ll mn;       // 子树最小值
    ll add;      // 子树整体加法的懒标记
    char rev;    // 子树待翻转的懒标记
    int siz;     // 子树大小
};

std::vector<Node> nd;

ll cnt = 0;  // 已用节点数
ll root = 0; // 根
std::vector<ll> A;

// 分配一个值为 v、父亲为 par 的新节点
ll new_node(ll v, ll par) {
    cnt++;
    nd[cnt].ch[0] = nd[cnt].ch[1] = 0;
    nd[cnt].fa = (int)par;
    nd[cnt].val = nd[cnt].mn = v;
    nd[cnt].add = 0;
    nd[cnt].rev = 0;
    nd[cnt].siz = 1;
    return cnt;
}

// 由左右孩子重算 x 的子树大小与最小值
void pull(ll x) {
    ll l = nd[x].ch[0], r = nd[x].ch[1];
    nd[x].siz = nd[l].siz + nd[r].siz + 1;
    ll m = nd[x].val;
    if (nd[l].mn < m) m = nd[l].mn;
    if (nd[r].mn < m) m = nd[r].mn;
    nd[x].mn = m;
}

// 从 x 往上逐层重算聚合值，直到根
void pull_up(ll x) {
    while (x) {
        pull(x);
        x = nd[x].fa;
    }
}

// 把 x 的懒标记下传一层：整子树加 add、整子树翻转
void push(ll x) {
    if (nd[x].add) {
        ll d = nd[x].add;
        nd[x].add = 0;
        for (int s = 0; s < 2; s++) {
            ll y = nd[x].ch[s];
            if (y) {
                nd[y].val += d;
                nd[y].mn += d;
                nd[y].add += d;
            }
        }
    }
    if (nd[x].rev) {
        nd[x].rev = 0;
        ll l = nd[x].ch[0], r = nd[x].ch[1];
        nd[x].ch[0] = (int)r;
        nd[x].ch[1] = (int)l;
        if (l) nd[l].rev ^= 1;
        if (r) nd[r].rev ^= 1;
    }
}

std::vector<ll> pathbuf;

// 把根到 x 路径上的懒标记自上而下清空
void push_path(ll x) {
    pathbuf.clear();
    while (x) {
        pathbuf.push_back(x);
        x = nd[x].fa;
    }
    for (size_t i = pathbuf.size(); i-- > 0;) {
        push(pathbuf[i]);
    }
}

// 把 x 上旋一层（路径上的懒标记已被 push_path 清空）
void rotate(ll x) {
    ll y = nd[x].fa;
    ll z = nd[y].fa;
    int side = (nd[y].ch[1] == (int)x) ? 1 : 0; // x 是 y 的哪一侧孩子
    ll w = nd[x].ch[side ^ 1];
    if (w) nd[w].fa = (int)y;
    nd[y].ch[side] = (int)w;
    nd[x].ch[side ^ 1] = (int)y;
    nd[y].fa = (int)x;
    nd[x].fa = (int)z;
    if (z) nd[z].ch[nd[z].ch[1] == (int)y ? 1 : 0] = (int)x;
    pull(y);
}

// 把 x 转成 goal 的孩子（goal=0 表示转成根）
void splay_to(ll x, ll goal) {
    push_path(x);
    while (nd[x].fa != goal) {
        ll y = nd[x].fa;
        ll z = nd[y].fa;
        if (z != goal && ((nd[z].ch[1] == (int)y) == (nd[y].ch[1] == (int)x))) {
            rotate(y); // 一字型先转父亲，避免退化成链
        }
        if (nd[x].fa != goal) rotate(x);
    }
    if (!goal) root = x; // 转到根后同步全局根指针
    pull(x);
    pull_up(nd[x].fa);
}

// 从 start 出发找中序第 k 个元素（沿途把懒标记下传）
ll kth(ll start, ll k) {
    ll x = start;
    while (true) {
        push(x);
        ll left = nd[nd[x].ch[0]].siz;
        if (k == left + 1) return x;
        if (k <= left) {
            x = nd[x].ch[0];
        } else {
            k -= left + 1;
            x = nd[x].ch[1];
        }
    }
}

// 把 A 的区间 [x, y] 切成一颗完整子树，返回 (a, 子树根)
void segment(ll x, ll y, ll& a, ll& key) {
    a = kth(root, x);
    splay_to(a, 0);
    ll b = kth(a, y + 2); // a 在根上用全局位置：A[y] 在 y+1，后继在 y+2
    splay_to(b, a);
    key = nd[b].ch[0];
}

// 翻转 A 的区间 [x, y]
void reverse_seg(ll x, ll y) {
    if (x >= y) return;
    ll a, key;
    segment(x, y, a, key);
    nd[key].rev ^= 1;
    pull_up(a);
}

// 区间右轮换 t 次：尾部 t 个移到前面，等价于三次翻转
void revolve(ll x, ll y, ll t) {
    t %= (y - x + 1);
    if (t) {
        reverse_seg(x, y - t);
        reverse_seg(y - t + 1, y);
        reverse_seg(x, y);
    }
}

// 把 A[lo..hi] 建成尽量平衡的子树，返回子树根
ll build(ll lo, ll hi, ll par) {
    if (lo > hi) return 0;
    ll mid = (lo + hi) >> 1;
    ll x = new_node(A[mid], par);
    nd[x].ch[0] = (int)build(lo, mid - 1, x);
    nd[x].ch[1] = (int)build(mid + 1, hi, x);
    pull(x);
    return x;
}

int main() {
    ll n;
    if (scanf("%lld", &n) != 1) return 0;
    A.assign(n, 0);
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &A[i]);
    }
    ll m;
    scanf("%lld", &m);

    ll cap = n + m + 5; // 左右哨兵 2 个 + 原序列 n 个 + 每次 INSERT 最多新增 1 个
    nd.assign(2 * cap + 10, Node());
    nd[0].mn = INF; // 空节点不能把子树最小值拉成 0

    A.push_back(INF); // 右哨兵并进建树列表
    ll head = new_node(INF, 0); // 左哨兵：树中第 1 个位置
    ll mid_root = build(0, n, head);
    nd[head].ch[1] = (int)mid_root;
    pull(head);
    root = head;

    std::vector<char> opname(16);
    for (ll q = 0; q < m; q++) {
        char buf[16];
        scanf("%s", buf);
        std::string op(buf);
        if (op == "ADD") {
            ll x, y, d;
            scanf("%lld %lld %lld", &x, &y, &d);
            ll a, key;
            segment(x, y, a, key);
            // 懒标记只打在子树根上：子树自身的最小值立即修正
            nd[key].val += d;
            nd[key].mn += d;
            nd[key].add += d;
            pull_up(a);
        } else if (op == "REVERSE") {
            ll x, y;
            scanf("%lld %lld", &x, &y);
            reverse_seg(x, y);
        } else if (op == "REVOLVE") {
            ll x, y, t;
            scanf("%lld %lld %lld", &x, &y, &t);
            revolve(x, y, t);
        } else if (op == "INSERT") {
            ll x, p;
            scanf("%lld %lld", &x, &p);
            ll a = kth(root, x + 1); // A 的第 x 个元素
            splay_to(a, 0);
            ll b = kth(a, x + 2);    // 全局位置：A[x] 在 x+1，后继在 x+2
            splay_to(b, a);
            ll c = new_node(p, b);
            nd[b].ch[0] = (int)c;    // 此刻 b 的左子树恰好为空
            pull(b);
            pull_up(a);
        } else if (op == "DELETE") {
            ll x;
            scanf("%lld", &x);
            ll a = kth(root, x);     // 树中第 x 个 = A 的第 x-1 个（可能是左哨兵）
            splay_to(a, 0);
            ll b = kth(a, x + 2);    // 全局位置：A[x] 在 x+1，后继在 x+2
            splay_to(b, a);
            nd[b].ch[0] = 0;         // 此刻 b 的左子树恰好只有 A[x]
            pull(b);
            pull_up(a);
        } else { // MIN
            ll x, y;
            scanf("%lld %lld", &x, &y);
            ll a, key;
            segment(x, y, a, key);
            printf("%lld\n", nd[key].mn);
        }
    }
    return 0;
}
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 18:41
# update_at: 2026-10-01 18:41

import sys

INF = 10**18  # 空子树与两个哨兵的最小值，保证永远不会成为 MIN 答案

# 用平行数组存 splay：0 号点表示空；树的中序 = [左哨兵, A1..An, 右哨兵]
ch: list[list[int]] = []     # ch[x] = [左孩子, 右孩子]
fa: list[int] = []           # 父亲
val: list[int] = []          # 节点自身的值
mn: list[int] = []           # 子树最小值
add: list[int] = []          # 子树整体加法的懒标记
rev: list[int] = []          # 子树待翻转的懒标记（push 时换左右孩子）
siz: list[int] = []          # 子树大小
cnt = 0                      # 已用节点数
root = 0
A: list[int] = []


def new_node(v: int, par: int) -> int:
    """分配一个值为 v、父亲为 par 的新节点。"""
    global cnt
    cnt += 1
    val[cnt] = mn[cnt] = v
    siz[cnt] = 1
    fa[cnt] = par
    ch[cnt] = [0, 0]
    return cnt


def pull(x: int) -> None:
    """由左右孩子重算 x 的子树大小与最小值。"""
    l, r = ch[x]
    siz[x] = siz[l] + siz[r] + 1
    mn[x] = min(val[x], mn[l], mn[r])


def pull_up(x: int) -> None:
    """从 x 往上逐层重算聚合值，直到根。"""
    while x:
        pull(x)
        x = fa[x]


def push(x: int) -> None:
    """把 x 的懒标记下传一层：整子树加 D、整子树翻转。"""
    if add[x]:
        d = add[x]
        add[x] = 0
        for s in ch[x]:
            if s:
                val[s] += d
                mn[s] += d
                add[s] += d
    if rev[x]:
        rev[x] = 0
        l, r = ch[x]
        ch[x] = [r, l]
        if l:
            rev[l] ^= 1
        if r:
            rev[r] ^= 1


def push_path(x: int) -> None:
    """把根到 x 路径上的懒标记自上而下清空。"""
    path = []
    while x:
        path.append(x)
        x = fa[x]
    for y in reversed(path):
        push(y)


def rotate(x: int) -> None:
    """把 x 上旋一层（x 及其祖先的懒标记此时都已被 push_path 清空）。"""
    y = fa[x]
    z = fa[y]
    side = ch[y][1] == x          # x 是 y 的哪一侧孩子
    w = ch[x][side ^ 1]
    if w:
        fa[w] = y
    ch[y][side] = w
    ch[x][side ^ 1] = y
    fa[y] = x
    fa[x] = z
    if z:
        ch[z][ch[z][1] == y] = x
    pull(y)


def splay_to(x: int, goal: int) -> None:
    """把 x 转成 goal 的孩子（goal=0 表示转成根），并把路径聚合值重算干净。"""
    global root
    push_path(x)
    while fa[x] != goal:
        y = fa[x]
        z = fa[y]
        if z != goal and (ch[z][1] == y) == (ch[y][1] == x):
            rotate(y)             # 一字型先转父亲，避免退化成链
        if fa[x] != goal:
            rotate(x)
    if not goal:
        root = x                  # 转到根后同步全局根指针
    pull(x)
    pull_up(fa[x])


def kth(start: int, k: int) -> int:
    """从 start 出发找中序第 k 个元素（沿途把懒标记下传）。"""
    x = start
    while True:
        push(x)
        left = siz[ch[x][0]]
        if k == left + 1:
            return x
        if k <= left:
            x = ch[x][0]
        else:
            k -= left + 1
            x = ch[x][1]


def segment(x: int, y: int) -> tuple[int, int]:
    """把 A 的区间 [x, y] 切成一颗完整子树，返回 (a, 子树根)。

    左哨兵占去树中第 1 个位置，A 的第 i 个元素在树中第 i+1 个。把
    a = 树中第 x 个（A[x-1] 或左哨兵）转到根，b = 树中第 y+2 个（A[y] 的后继）
    转成 a 的孩子，b 的左子树恰好就是整个区间。
    """
    a = kth(root, x)
    splay_to(a, 0)
    b = kth(a, y + 2)             # a 在根上用全局位置：A[y] 在 y+1，后继在 y+2
    splay_to(b, a)
    return a, ch[b][0]


def reverse_seg(x: int, y: int) -> None:
    """翻转 A 的区间 [x, y]。"""
    if x >= y:
        return
    a, key = segment(x, y)
    rev[key] ^= 1
    pull_up(a)


def revolve(x: int, y: int, t: int) -> None:
    """区间右轮换 t 次：尾部 t 个移到前面，等价于三次翻转。

    设段为 A B（A 是前 len-t 个，B 是后 t 个），目标是 B A；
    而 (A^r B^r)^r = B A，所以依次翻 A、翻 B、整段再翻。
    """
    t %= y - x + 1
    if t:
        reverse_seg(x, y - t)
        reverse_seg(y - t + 1, y)
        reverse_seg(x, y)


def build(lo: int, hi: int, par: int) -> int:
    """把 A[lo..hi] 建成尽量平衡的子树，返回子树根。"""
    if lo > hi:
        return 0
    mid = (lo + hi) >> 1
    x = new_node(A[mid], par)
    ch[x][0] = build(lo, mid - 1, x)
    ch[x][1] = build(mid + 1, hi, x)
    pull(x)
    return x


def solve() -> None:
    global root, cnt, A
    it = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    n = int(next(it))
    A = [int(next(it)) for _ in range(n)]
    m = int(next(it))

    # 容量：左右哨兵 2 个 + 原序列 n 个 + 每次 INSERT 最多新增 1 个
    cap = n + m + 5
    for arr in (ch, fa, val, mn, add, rev, siz):
        arr.extend([0] * (2 * cap))  # ch 需要成对占位，多开一倍更省心
    mn[0] = INF                      # 空节点不能把子树最小值拉成 0

    A.append(INF)                    # 右哨兵并进建树列表，保证任何后继都存在
    head = new_node(INF, 0)          # 左哨兵：树中第 1 个位置
    mid_root = build(0, n, head)     # 依次为 A1..An、右哨兵
    ch[head][1] = mid_root
    pull(head)
    root = head

    for _ in range(m):
        op = next(it)
        if op == b'ADD':
            x, y, d = int(next(it)), int(next(it)), int(next(it))
            a, key = segment(x, y)
            # 懒标记只打在子树根上：子树自身的最小值立即修正
            val[key] += d
            mn[key] += d
            add[key] += d
            pull_up(a)
        elif op == b'REVERSE':
            reverse_seg(int(next(it)), int(next(it)))
        elif op == b'REVOLVE':
            revolve(int(next(it)), int(next(it)), int(next(it)))
        elif op == b'INSERT':
            x, p = int(next(it)), int(next(it))
            a = kth(root, x + 1)     # A 的第 x 个元素
            splay_to(a, 0)
            b = kth(a, x + 2)        # 全局位置：A[x] 在 x+1，后继在 x+2（可能是右哨兵）
            splay_to(b, a)
            c = new_node(p, b)
            ch[b][0] = c             # 此刻 b 的左子树恰好为空
            pull(b)
            pull_up(a)
        elif op == b'DELETE':
            x = int(next(it))
            a = kth(root, x)         # 树中第 x 个 = A 的第 x-1 个（可能是左哨兵）
            splay_to(a, 0)
            b = kth(a, x + 2)        # 全局位置：A[x] 在 x+1，后继在 x+2
            splay_to(b, a)
            ch[b][0] = 0             # 此刻 b 的左子树恰好只有 A[x]
            pull(b)
            pull_up(a)
        else:                        # MIN
            x, y = int(next(it)), int(next(it))
            _, key = segment(x, y)
            out.append(str(mn[key]))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

Python 版按教学短解法风格实现：平行数组存树、迭代 splay（免递归爆栈）、两个哨兵。同样的算法落地到 C++ 就是常见的 ch/fa/val/mn/add/rev/siz 数组 + rotate/splay/push/pull 模板，逻辑一一对应。

复杂度

  • 时间：建树 O(n)O(n)；每次操作常数次 splay / kth，均摊 O(log⁡n)O(\log n)，总计 O((n+M)log⁡n)≈105×17O\big((n+M)\log n\big) \approx 10^5 \times 17，与 C++ 正解同阶。Python 常数较大，OJ 1s 限内可能 TLE（本地放宽 10 倍限时后最强数据 4.3s 通过），按约定接受，不改为暴力。
  • 空间：O(n+M)O(n + M) 个节点（每次 INSERT 至多新增一个），平行数组存下，最强大的测点峰值约 92MB。

总结

  • 序列被翻转、轮换、插删，位置信息不可靠 ⇒ 用平衡树的中序表示序列，“区间”=“完整子树”。
  • 两次 splay 切出区间子树后，ADD/REVERSE 打懒标记，MIN 读根，INSERT/DELETE 在相邻位置间 O(1)O(1) 修补指针。
  • REVOLVE 用恒等式 (ArBr)r=B A(A^r B^r)^r = B\,A 化成三次翻转，不写任何循环移位。
  • 两个 +∞+\infty 哨兵让"前驱/后继"永远存在，边界统一；空节点 mn 也置 +∞+\infty，防止污染子树最小值。

图示解析

整体路线：一段序列在树中始终是"中序连续段"，任何区间操作都走同一条"定位 → 切出 → 碰根 → 合回"的流水线：

flowchart LR
    K["kth 定位<br/>（沿途 push 懒标记）"] --> S["两次 splay<br/>切出区间子树"]
    S --> T{"操作类型"}
    T -- ADD/REVERSE --> L["子树根打懒标记"]
    T -- REVOLVE --> V["三次 REVERSE 复用翻转"]
    T -- MIN --> M["读子树根 mn"]
    T -- INSERT/DELETE --> P["前驱-后继之间<br/>O(1) 接/摘叶子"]
    L --> U["pull 上收，哨兵复位"]
    V --> U
    M --> U
    P --> U

读者只需盯住一点：无论哪种操作，被修改的都只有"切出来的那颗子树的根"（插删是它旁边的两个指针），其余节点原封不动。这正是均摊 O(log⁡n)O(\log n) 的结构保证。