G.: Path queries on weighted trees

Abstract. We consider the problem of supporting several different path queries over a tree on n nodes, each having a weight drawn from a set of σ distinct values, where σ ≤ n. One query we support is the path median query, which asks for the median weight on a path between two given nodes. For this and the more general path selection query, we present a linear space data structure that answers queries in O(lg σ) time under the word RAM model. This greatly improves previous results on the same problem, as previous data structures achieving O(lgn) query time use O(n lg2 n) space, and previous linear space data structures require O(n) time to answer a query for any positive constant [16]. Our linear space data structure also supports path counting queries in O(lg σ) time. This matches the result of Chazelle [8] when σ is close to n, but has better performance when σ is significantly smaller than n. Finally, the same data structure can also support path reporting queries inO(lg σ+occ lg σ) time, where occ is the size of output. In addition, we present a data structure that answers path reporting queries in O(lg σ+occ lg lg σ) time, using O(n lg lg σ) space. These are the first data structures that answer path reporting queries.