type
status
date
slug
summary
tags
category
icon
password
平常在信息学竞赛中求 一般有四种办法
- 倍增法求解，预处理复杂度是 ，每次询问的复杂度是
- 利用欧拉序转化为 问题，用 表求解 问题，预处理复杂度，每次询问的复杂度为
- 采用 算法求解，复杂度
- 利用树链剖分求解，复杂度预处理 ，单次查询
下面将详细地介绍”用欧拉序转换为RMQ问题”
用欧拉序转换为RMQ问题
温馨提示，若想更好地阅读本文章，你需要掌握一下知识：
- 可以dfs一棵树
- 熟知st表
数组下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
欧拉序列 | 1 | 2 | 4 | 2 | 5 | 2 | 1 | 3 | 6 | 3 | 1 |
深度 | 1 | 2 | 3 | 2 | 3 | 2 | 1 | 2 | 3 | 2 | 1 |
对有根树进行 ，无论是递归还是回溯，每次到达一个结点时都将深度记录下来，这个东西叫做欧拉序列，其长度为
把节点 在欧拉序列中第一次出现的序号记为 。有了欧拉序列， 问题可以在线性时间内化为 问题 ，即 ，这里RMQ返回的是深度最小的值所对应的节点
若需求两个点的距离，利用 可以求得
仔细想一下，从 走到 的过程中一定会经过 ，但不会经过 的祖先。因此，从 走到 的过程中经过的深度最小的结点就是
用dfs计算欧拉序列的时间复杂度 ，空间复杂度 ，所以 问题可以在 的时间内用 的空间转化成等规模的 问题
此处引用刘汝佳《算法竞赛入门经典》并做适当修改
计算欧拉序列：
现在已经知道深度了，先预处理一下 ：
整体思路就是这样