کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430932 | 688233 | 2012 | 6 صفحه PDF | دانلود رایگان |

We consider the problem of succinctly representing a given vertex-weighted tree of n vertices, whose vertices are labeled by integer weights from {1,2,…,σ}{1,2,…,σ} and supporting the following path queries efficiently:
• Path median query: Given two vertices i, j, return the median weight on the path from i to j.
• Path selection query: Given two vertices i, j and a positive integer k, return the kth smallest weight on the path from i to j.
• Path counting/reporting query: Given two vertices i, j and a range [a,b][a,b], count/report the vertices on the path from i to j whose weights are in this range.The previous best data structure supporting these queries takes O(nlogn) bits space and can perform path median/selection/counting in O(logσ) time and path reporting in O(logσ+occlogσ) time, where occ represents the number of outputs [M. He, J.I. Munro, G. Zhou, Path queries in weighted trees, in: International Symposium on Algorithms and Computation, 2011, pp. 140–149]. We present a succinct data structure taking nlogσ+6n+o(nlogσ) bits space that can perform the above mentioned queries in O(logσlogn) and O(logσlogn+occlogσ) time respectively.
Journal: Journal of Discrete Algorithms - Volume 17, December 2012, Pages 103–108