I came across this paper
On Finding Lowest Common Ancestors: Simplification and Parallelization by Baruch Schieber, Uzi Vishkin April, 1987
so naturally I tried to code golf it
lca https://judge.yosupo.jp/submission/188189
rmq https://judge.yosupo.jp/submission/188190
edit: minor golf
Cool! This algorithm seems to be almost the same size of the one described here, although maybe a bit slower.
rip
although looking at the test cases, this approach does worse on the small width query where the usual 4-russians approach would have an advantage: you hit the case with less operations
on cses rmq: your implementation: .10s, my implementation: 0.12s
Kudos for a clean, neat code and usage of C++20 features!
thanks
Auto comment: topic has been updated by lrvideckis (previous revision, new revision, compare).