ETT学习笔记（持续更新）

2024-04-06 21:41:08

-1.什么是ETT / 为什么要学ETT

ETT是一种化学物质，分子式是C3H6N4S

ETT全名Eular Tour Tree，是一种~~玄学的~~维护动态树的数据结构。支持子树加，改父亲，求某个点到根的路径。

学ETT的理由：

特别好写，特别好调
一只log跑得快
可以支持动态树的大部分操作
~~不想学LCT~~

0.前置知识

0.1 欧拉序

既然有Eular，自然离不开欧拉序。这个东西在ST表 \(O(1)\) 求LCA中用到过，若不会请自行学习。

但是这里我们并不是用求LCA的那个欧拉序，而是稍微变形一下。这个在后面会讲到。

0.2 平衡树

这个不会的话，左转洛谷模板区包你学会。

正常情况下，常用的平衡树任选一种均可。

1.ETT的基础操作

1.1 如何用括号序序维护子树信息。

为了维护第1,3个操作，我们需要使用一种特殊的序列——括号序，即：每个点访问时记录，退出时再记录。

void dfs(int u)
{
    //push u
    for(int v:rd[u]) dfs(v);
    //push u
}

可以发现，这种括号序中每个点出现且仅出现2次。

比如上图，括号序就是12334556421（结果不唯一）。

我们考虑这样一种括号序有什么特殊性质：

一个节点的子树的节点都是连续的。
一个点 \(v\) 在 \(u\) 到根路径上当且仅当 \(v\) 在欧拉序中 \(u\) 第一次出现的位置前出现且仅出现一次。

第一个性质和dfs序类似，显然成立。考虑如何证明第二个性质：

如果我们将一个点第一次记录视为插入栈，第二次记录视为从栈中删除，显然可以发现访问到一个点时，栈中的元素都是它到根的路径。

如上图，绿线表示第一次记录，红线表示第二次记录。蓝色表示记录一次，棕色表示记录两次。显然访问5时1,2,4,5被记录一次。

可以发现 \(u\) 到根路径上的点就是栈中只被记录一次的点，所以显然有第二个性质成立。

考虑如何利用这个性质：子树加显然就是区间修改，那么询问一个点到根的路径上点权和怎么办。

由于我们只需要被记录一次的点的点权和，考虑在第二次记录的时候把第一次记录的结果撤销。具体来说，一个结点第一次被记录时在序列中插入他的点权，第二次被记录时插入他的点权的相反数。

void dfs(int u)
{
    //push w[u]
    for(int v:rd[u]) dfs(v);
    r[u]=newnode(w[u],-1);
    //push -w[u]
}

可以发现，我们只需要对该点第一次出现位置求一次前缀和，就可以知道它到根的路径的点权和。这样我们就完成了除了改父亲之外的所有操作。

1.2 如何用ETT维护动态树

在此之前，我们已经能够处理 \(66.7\%\) 的操作了。但是好像至今为止所有的操作都可以用树剖来完成。。。

所以接下来就是维护动态树最重要的部分：改父亲。

我们考虑改父亲对括号序有什么要求：

其实可以发现，子树内部的括号序是不会变的，只是括号序整体的位置有所变化。

举个例子：

考虑上图，\(u\) , \(v\) 是两颗子树，不妨用 \(\text{{u}}\)，\(\text{{v}}\) 表示子树部分的欧拉序。按照1.1，我们可以写出它的一种括号序：

12334{u}{v}425667751

考虑我们将4的父亲改成5：

我们可以再写出它的一种括号序：

1233254{u}{v}4667751

可以发现，4的子树部分的欧拉序并没有改变。变化的实质是 \(\text{4{u}{v}4}\) 这段括号序向后移动了2个单位。

可以发现什么？假如我们用 \(\text{{u}}\) 表示 \(u\) 的子树的欧拉序，那么将 \(u\) 的父亲改为 \(v\) 本质就是把 \(\text{{u}}\) 移动到 \(v\) 在欧拉序中第一次出现的位置。

那么我们怎么维护呢？这本质是区间移动的过程，其实大部分平衡树都支持这种操作。不妨用平衡树维护序列的位置（注意不是数值），即改平衡树中序遍历的结果就是整个序列

特别的，由于我们需要查找某个节点第一次出现的位置。我们不妨记录下第一次出现的位置所代表的节点。那么它在平衡树上的位置就是序列中第一次出现的位置。

这个就比较好求了。每次不断跳在平衡树上的父亲记录经过的节点数。特别的，如果当前节点是其父亲的右儿子，那么还要加上左儿子 \(\text{size}\)。

我这里采用的是fhq-treap，因为这个平衡树自带split和merge操作，不用特别处理平衡树移动这种操作。

关键代码：

split(root,kth(l[x])-1,lt,mt);//kth(u)是求u在平衡树中的位置
split(mt,kth(r[x]),mt,rt);//提取出l[u]~r[u]
st=merge(lt,rt);//将非l[u]~r[u]部分合并
split(st,kth(l[y]),lt,rt);//提取出l[y]，即要插入的节点
rt=merge(merge(lt,mt),rt);

这样，我们就完成了用ETT维护动态树的操作。

码农公寓