Euler Tour Tree
任何一颗树都能够用欧拉旅行路径来表示,欧拉旅行路径是一个序列,他记录了一颗树的dfs的时候的顺序,记录了进入每个节点的时间和退出该节点的时间,这样以后,子树就成了ETT上连续的区间
,当我们对子树进行交换的时候,我们就可以将这个区间平移。这里我们用splay维护即可
- 本文作者: fightinggg
- 本文链接: http://fightinggg.github.io/yilia/yilia/Q2JVXK.html
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!