Path Queries in Weighted Trees

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 \sigma)$

time under the word RAM model. This greatly improves previous results on the same problem, as previous data structures achieving

$O(\lg n)$

query time use

$O(n \lg^2 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 \sigma)$

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 in

$O(\lg \sigma + occ \lg \sigma)$

time, where

occ

is the size of output. In addition, we present a data structure that answers path reporting queries in

$O(\lg \sigma + occ \lg\lg\sigma)$

time, using

$O(n\lg\lg\sigma)$

space. These are the first data structures that answer path reporting queries.