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计算欧拉序列的时间复杂度 ,空间复杂度 ,所以 问题可以在 的时间内用 的空间转化成等规模的 问题
此处引用刘汝佳《算法竞赛入门经典》并做适当修改
计算欧拉序列:
现在已经知道深度了,先预处理一下 :
整体思路就是这样