关于快速LCA

学术版

ppip @ 2023-04-09 07:21:21

有没有一种不需要线性rmq的实现O(\log n)求O(\log n)个点LCA的方法？

by Demeanor_Roy @ 2023-04-09 08:02:00

dfn 最小的点与 dfn 最大点的 lca ？

by Demeanor_Roy @ 2023-04-09 08:03:04

不知道记错没有

by ppip @ 2023-04-09 08:15:14

@Demeanor_Roy 应该是的orz

by _maojun__ @ 2023-04-09 09:08:48

嗯，线性 rmq 不是直接整到 O(n+m) 吗

为什么还带个 log

|