Timeline for How to make efficient path minimum queries in a tree?

Current License: CC BY-SA 4.0

9 events

when toggle format	what		by	license	comment
Jan 20, 2021 at 0:02	history	edited	Steven	CC BY-SA 4.0	added 1743 characters in body
Jan 19, 2021 at 21:51	history	edited	Steven	CC BY-SA 4.0	deleted 3 characters in body
Jan 19, 2021 at 21:45	history	edited	Steven	CC BY-SA 4.0	deleted 3 characters in body
Jan 19, 2021 at 21:45	comment	added	Steven		@j_random_hacker. You are right, my writeup is missing one ingredient. The current solution supports queries in $O(\log n)$ time, but adding a long-path decomposition of the tree it is possible to achieve a $O(1)$ query time. I've edited my answer to increase the claimed query time. I'll add more details on how to obtain the $O(1)$ query time in a couple of hours. Thanks for noticing this!
Jan 19, 2021 at 19:10	comment	added	j_random_hacker		When using your simpler approach, I don't see how the final RMQ lookups can be done in $O(1)$ time: Unlike in the initial RMQ lookup done to find the LCA (which is performed in an array where we have $O(1)$ random access), we can't just jump directly to the $k$-th ancestor of an arbitrary vertex -- unless we have done $O(n^2)$ preprocessing, no? The best approach I can think of is to jump "up" the path towards the root in exponentially smaller steps until hitting the LCA, making the queries $O(\log n)$ (or $O(\log \log n)$ if all outdegrees are > 1).
Jan 19, 2021 at 17:21	comment	added	Steven		@D.W. The solution I described here requires $O(n \log n)$ space. More elaborate solutions only require $O(n)$ space are described in the paper I linked. I'll try to clarify this in the answer.
Jan 19, 2021 at 17:20	history	edited	Steven	CC BY-SA 4.0	added 11 characters in body
Jan 19, 2021 at 17:17	history	edited	Steven	CC BY-SA 4.0	added 11 characters in body
Jan 19, 2021 at 17:12	history	answered	Steven	CC BY-SA 4.0