Euler Tour Tree（ETT，欧拉游览树）

What · 是什么

ETT 是一种动态树数据结构：对一棵树做 DFS，访问节点或遍历有向边时记录一次，得到欧拉游览表示（Euler Tour Representation, ETR）序列（长度 3n-2，若把点视作自环）。原树的结构与序列结构一一对应，因此『树上连边』等价于『把两个序列拼接』，『断边』等价于『把序列拆开』，『换根』等价于『把序列旋转』。用一个支持区间拆分/合并与区间修改查询的平衡树（Splay 或非旋 Treap）维护序列，所有动态树操作都能在 O(log n) 完成。相比 LCT 更擅长维护子树信息（子树最值、子树和），因为子树在 ETR 中是连续区间。

Why · 为什么

How · 实现

伪代码

# 用非旋 Treap 维护 ETR 序列
# 序列元素 = 节点访问（进入/自环/有向边）。为简洁，以下用节点自环表示法。

MakeRoot(u):
    L = treap_of(u 所在树)
    split L at 元素(u) -> L1, L2   # L1 含 (u,u) 及之前，L2 其余
    return merge(L2, L1)

Insert(u, v):  # u∈T1, v∈T2，连边 (u,v)
    (L1a, L1b) = split_at_u(L1)
    (L2a, L2b) = split_at_v(L2)
    return merge(merge(L1b, L1a), 边(u,v), L2b, L2a, 边(v,u))

Delete(u, v):  # 删边 (u,v)，序列中出现 [(u,v)] 与 [(v,u)]
    split L -> L1, [uv], L2, [vu], L3
    return (merge(L1, L3), L2)   # 两棵新树

QuerySubtree(u):
    return range_query(区间 [first(u), last(u)])

Python 实现

import random

class TreapNode:
    __slots__ = ('key', 'prio', 'left', 'right', 'sz', 'val', 'sm')
    def __init__(self, key, val):
        self.key = key
        self.prio = random.random()
        self.left = self.right = None
        self.sz = 1
        self.val = val
        self.sm = val

def _sz(t):
    return t.sz if t else 0

def _sm(t):
    return t.sm if t else 0

def _pull(t):
    if t:
        t.sz = 1 + _sz(t.left) + _sz(t.right)
        t.sm = t.val + _sm(t.left) + _sm(t.right)

def split(t, k):
    """按前 k 个元素切开，返回 (左, 右)"""
    if not t:
        return None, None
    if _sz(t.left) >= k:
        a, b = split(t.left, k)
        t.left = b
        _pull(t)
        return a, t
    else:
        a, b = split(t.right, k - _sz(t.left) - 1)
        t.right = a
        _pull(t)
        return t, b

def merge(a, b):
    if not a or not b:
        return a or b
    if a.prio > b.prio:
        a.right = merge(a.right, b)
        _pull(a)
        return a
    else:
        b.left = merge(a, b.left)
        _pull(b)
        return b

def build_seq(keys):
    t = None
    for k in keys:
        t = merge(t, TreapNode(k, 0))
    return t

def pos_of(root, key):
    """返回 key 首次出现的位置（0 基）"""
    def walk(t, key, acc):
        if not t:
            return None
        if t.key == key:
            return acc + _sz(t.left)
        r = walk(t.left, key, acc)
        if r is not None:
            return r
        return walk(t.right, key, acc + _sz(t.left) + 1)
    return walk(root, key, 0)

def euler_tour_tree_selfcheck():
    random.seed(1)
    # 树: 1-2, 1-3；节点集合做 ETR 的简化模型：每个节点出现一次
    # 用『节点自环』序列直接验证 MakeRoot/Insert/Delete 的位置不变式
    # 完整 ETR 需要 (u,u),(u->v),(v->u) 三元素/边，此处给出可运行的简化自测：
    # 以 entry 序列 [1,2,3] 表示树，验证序列操作正确性
    root = build_seq([1, 2, 3])
    assert _sz(root) == 3
    assert pos_of(root, 2) == 1
    # MakeRoot(2): 序列旋转 -> [2,3,1]
    p = pos_of(root, 2)
    a, b = split(root, p)
    root = merge(b, a)
    assert pos_of(root, 1) == 2
    print('ETT sequence ops OK')

if __name__ == '__main__':
    euler_tour_tree_selfcheck()

易错点

• ETR 长度为 3n-2，用点自环表示的简化实现会丢边信息，仅作教学
• Insert/Delete 的序列拼接顺序必须严格按欧拉回路拼接规则，顺序错导致树结构错误
• 换根 (MakeRoot) 本质是旋转欧拉回路，必须在 (u,u) 处断开再拼
• 查询子树要先定位 first(u)/last(u) 的区间端点，端点定位错误会得到错误区间
• Treap 递归深度依赖随机优先级，随机种子固定可复现但需保证平衡

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/ds/ett.md
• OI Wiki△ https://oi-wiki.org/ds/ett/