2023/11/27 by Philip Bille, Yakov Nekrich, Bille, Philip +3
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2311.15777
openalex publication_date 2023/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The weighted ancestor problem on a rooted node-weighted tree T is a generalization of the classic predecessor problem: construct a data structure for a set of integers that supports fast predecessor queries. Both problems are known to require Ω(loglog n) time for queries provided O(n poly log n) space is available, where n is the input size. The weighted ancestor problem has attracted a lot of attention by the combinatorial pattern matching community due to its direct application to suffix trees. In this formulation of the problem, the nodes are weighted by string depth. This research has culminated in a data structure for weighted ancestors in suffix trees with O(1) query time and an O(n)-time construction algorithm [Belazzougui et al., CPM 2021]. In this paper, we consider a different version of the weighted ancestor problem, where the nodes are weighted by any function \textsfweight that maps the nodes of T to positive integers, such that \textsfweight(u)≤ \textsfsize(u) for any node u and \textsfweight(u1)≤ \textsfweight(u2) if node u1 is a descendant of node u2, where \textsfsize(u) is the number of nodes in the subtree rooted at u. In the size-constrained weighted ancestor (SWA) problem, for any node u of T and any integer k, we are asked to return the lowest ancestor w of u with weight at least k. We show that for any rooted tree with n nodes, we can locate node w in O(1) time after O(n)-time preprocessing. In particular, this implies a data structure for the SWA problem in suffix trees with O(1) query time and O(n)-time preprocessing, when the nodes are weighted by \textsfweight. We also show several string-processing applications of this result.