Data Structures for Path Queries

摘要

Consider a tree T on n nodes, each having a weight drawn from [1..sigma]. In this article, we study the problem of supporting various path queries over the tree T. The path counting query asks for the number of the nodes on a query path whose weights are in a query range, while the path reporting query requires to report these nodes. The path median query asks for the median weight on a path between two given nodes, and the path selection query returns the k-th smallest weight. We design succinct data structures to encode T using nH(W-T) + 2n + o(n lg sigma) bits of space, such that we can support path counting queries in O(lg sigma / lg lg n + 1) time, path reporting queries in O((occ + 1)(lg sigma / lg lg n + 1)) time, and path median and path selection queries in O(lg sigma / lg lg sigma) time, where H(W-T) is the entropy of the multiset of the weights of the nodes in T and occ is the size of the output. Our results not only greatly improve the best known data structures [Chazelle 1987; Krizanc et al. 2005], but also match the lower bounds for path counting, median, and selection queries [Patrascu 2007, 2011; Jorgensen and Larsen 2011] when sigma = Omega (n/polylog(n)).