Fast Leaf-to-Ancestor Minimum Query in the Oracle Model

Aleksey Upirvitskiy †, Aleksandr Levin ∗ · 2026

Read Fast Leaf-to-Ancestor Minimum Query in the Oracle Model by Aleksey Upirvitskiy †, Aleksandr Levin ∗ (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14112.txt.

Introduction

Upirvitskiy and Levin give a fast structure for leaf-to-ancestor minimum queries on rooted weighted trees in the oracle model. There, only comparisons of edge or node weights may read values. After preprocessing in O(n log h) time, space and oracle calls, any query answers in O(1) worst-case time, making no oracle calls at query time. The method fuses conversion of edge weights to node weights with a deterministic tie-break, ladder decomposition, binary lifting, and sparse-table range-minimum queries.

Catalog record

CREATORAleksey Upirvitskiy †, Aleksandr Levin ∗
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25251
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14112

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model Aleksey Upirvitskiy †, Aleksandr Levin ∗ Abstract 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 ) O(n\log h) preprocessing time, space, and oracle calls (where n n is the number of nodes and h h is the tree height), answers any leaf-to-ancestor query in O ⁡ ( 1 ) 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. 1 Introduction The path minimum query is a classic theoretical computer science problem of finding the smallest value along the simple path between two given nodes of a tree. One of the variants is a leaf-to-ancestor minimum query in the oracle model which is used by Tianqi Yang in [ 1 ] to verify the randomized minimum spanning Boruvka trees. The original paper shows that if there exists a solution to this problem with O(n\log h) preprocessing time and O(1) query time without additional comparisons, then the number of comparisons in the verification process can be decreased. In this paper we discuss such a solution and show its optimality. 1.1 Path minimum query with Oracle Firstly, let us properly formulate the problem. Given a rooted tree with n nodes and height h , where each edge has a certain hidden value, and an Oracle function which implements the comparison between two edges, the goal of the algorithm is to answer queries in the form of ”find the minimum element on the path from a given leaf to its ancestor”. Throughout the paper, 0pt(v) is the number of edges on the path from the root to v , so the root has depth 0 and the height of the tree is the maximum depth of a vertex, \max_{v\in V(T)}0pt(v) . Oracle is a black-box function that takes two edge identifiers as input and returns true if and only if the value associated with the first edge is smaller than the value associated with the second edge. The algorithm asymptotics depends on the triplet of the preprocessing time, the number of oracle queries during querying, and the query time, which is additional time in the word RAM model (meaning that random-access machine does arithmetic and bitwise operations on a word of w bits). 1.2 Borůvka trees and query structures Given a weighted, connected graph, a minimum spanning tree is a spanning tree with minimum total edge weight. Minimum spanning tree verification reduces to path queries on a candidate spanning tree: for each non-tree edge, its weight is compared with the maximum edge weight on the tree path between its endpoints. King [ 2 ] constructs a Borůvka tree for this verification problem and shows that the relevant path maximum is preserved on the corresponding path between leaves of the auxiliary tree. Yang [ 1 ] uses the analogous Borůvka-tree setting for tree-path minimum queries and proposes a query structure for this problem. The structure is designed for repeated online queries after preprocessing: path-minimum information is stored on the auxiliary tree so that a query can be answered without scanning the queried path. Yang’s algorithm has four steps: (1) construct a balanced Borůvka tree from the input graph so that all leaves are at the same depth; (2) for subtrees of small depth, compute path minima using Cartesian trees; (3) for all other parts, split the depth into layers whose width is defined by the inverse Ackermann function on the k -th row, \lambda_{k}(n)=\min\{\,j\geq 1:A(k,j)\geq n\,\}, and precompute minima as correspondences {vertex \to its predecessor on the layer boundary}; (4) repeat this step with thresholds that depend on the current stage of the algorithm. Yang’s construction achieves two outcomes: either \{O(n\log\lambda_{k}(n)),\,2k,\,O(k+\log\lambda_{k}(n))\}, or \{O(n\log\lambda_{k}(n)),\,2k+2,\,O(k)\}. This paper’s result combines the comparison bound of the first variant with the query time of the second one, with the same asymptotic preprocessing bound. 2 Preliminaries 2.1 Ladder decomposition A ladder decomposition is a tree preprocessing technique used to accelerate queries on ancestor-directed paths and is closely related to level-ancestor structures [ 3 ] . A path between two arbitrary vertices is not necessarily ancestor-directed: it can be split at their lowest common ancestor into two upward paths, one from each endpoint to this ancestor. For the path-minimum queries considered here, the answer on the whole path is obtained by combining the minima on these two parts. The construction consists of two parts. First, the vertices are partitioned into disjoint base paths by a longest-path decomposition. Then each base path is extended upward by adding ancestors of its highest vertex, until either its length is doubled or the root is reached. Thus base paths form a partition of the tree, whereas the resulting ladders may overlap in the added ancestor vertices. This extension gives, for every vertex of a base path, a contiguous array of ancestors that can be used for fast upward jumps. Building the longest-path decomposition The longest-path decomposition breaks the tree into disjoint longest-path layers. It can be built in linear time as follows: 1. For each node, compute the maximum distance from that node down to a leaf: it is 0 for a leaf, and 1+\max\{\mathrm{down}(\mathrm{child})\} otherwise. 2. For every non-leaf node, choose one child that attains the maximum \mathrm{down} value, and keep only the edge to that child. 3. After removing all other child edges, the tree splits into a forest of paths. These paths form the longest-path decomposition. In the data structures below we store every path from its deepest node toward the root. Thus a path can be represented by the deepest node and by the number of vertices in the path: (v,\ell)\longrightarrow[\,v,\operatorname{pre}_{1}(v),\operatorname{pre}_{2}(v),\ldots,\operatorname{pre}_{\ell-1}(v)\,], where \operatorname{pre}_{i}(v) denotes the ancestor of v at distance i ( \operatorname{pre}_{1}(v) is the parent of v , \operatorname{pre}_{2}(v) is the parent of \operatorname{pre}_{1}(v) , etc.). Building the ladder decomposition Building the ladder decomposition can be done in linear time by appending some nodes to every path of the longest path decomposition. It is equivalent to changing every pair of nodes by the rule: (v,\ell)\to(v,\min(2\ell,0pt(v)+1)). The term 0pt(v)+1 is the number of vertices on the path from the root to v , so it is the largest possible length of a ladder ending at v . The ladder obtained from a longest-path component is called the base ladder of the vertices of that component. For every vertex we store a pointer to its base ladder; for each base ladder we store its deepest vertex. This algorithm works in O(n) time, because longest-path decomposition can be easily built in such time, and total length of paths is n , so doubling it works in O(n) as well. Lemma 1 Let x be a node with a descendant at distance L .

Read the complete text