Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
This work provides an optimal solution for a fundamental query problem in the oracle model, benefiting applications where edge weights are compared via an oracle.
The paper presents a static data structure for leaf-to-ancestor minimum queries on a rooted weighted tree in the oracle model, achieving O(1) query time with zero oracle calls after O(n log h) preprocessing. The preprocessing oracle complexity is proven tight in the deterministic comparison model.
We study leaf-to-ancestor path-minimum queries on a rooted, weighted tree in the oracle model, where the only allowed value operation is a comparison oracle on edge (or node) weights. We give a static data structure that, after O(n log h) preprocessing time, space, and oracle calls (where $n$ is the number of nodes and $h$ is the tree height), answers any leaf-to-ancestor query in O(1) worst-case time with zero oracle calls at query time. The method combines (I) an edge-to-node weight conversion with a deterministic tie-break to obtain a total order; (II) ladder (longest-path) decomposition; (III) binary lifting; and (IV) sparse-table RMQ built over ladder arrays, storing indices selected via the oracle during preprocessing. We also show that the preprocessing oracle-comparison bound is tight in the deterministic comparison model.