# zbMATH — the first resource for mathematics

Succinct representations of weighted trees supporting path queries. (English) Zbl 1268.68069
Summary: 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,\ldots ,\sigma\}$$ and supporting the following path queries efficiently: (1) path median query: given two vertices $$i$$, $$j$$, return the median weight on the path from $$i$$ to $$j$$, (2) path selection query: given two vertices $$i$$, $$j$$ and a positive integer $$k$$, return the $$k$$th smallest weight on the path from $$i$$ to $$j$$, (3) path counting/reporting query: given two vertices $$i$$, $$j$$ and a range $$[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(n\log n)$$ bits space and can perform path median/selection/counting in $$O(\log\sigma )$$ time and path reporting in $$O(\log \sigma +occ\log \sigma )$$ time, where $$occ$$ represents the number of outputs [M. He et al., Lect. Notes Comput. Sci. 7074, 140–149 (2011; Zbl 1350.68073)].
We present a succinct data structure taking $$n\log \sigma +6n+o(n\log \sigma )$$ bits space that can perform the above mentioned queries in $$O(\log \sigma \log n)$$ and $$O(\log \sigma \log n+occ\log \sigma )$$ time respectively.

##### MSC:
 68P05 Data structures 68R10 Graph theory (including graph drawing) in computer science 05C05 Trees
##### Keywords:
succinct data structures
Full Text:
##### References:
  N. Alon, B. Schieber, Optimal preprocessing for answering on-line product queries, Tech. Rep., Tel Aviv University, 1987.  Benoit, D.; Demaine, E.D.; Munro, J.I.; Raman, R.; Raman, V.; Rao, S.S., Representing trees of higher degree, Algorithmica, 43, 4, 275-292, (2005) · Zbl 1086.68034  Chazelle, B., Computing on a free tree via complexity-preserving mappings, Algorithmica, 2, 337-361, (1987) · Zbl 0636.68092  D.R. Clark, J.I. Munro, Efficient suffix trees on secondary storage (extended abstract), in: ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 383-391. · Zbl 0847.68030  Cole, R.; Farach-Colton, M.; Hariharan, R.; Przytycka, T.M.; Thorup, M., An $$O(n \log n)$$ algorithm for the maximum agreement subtree problem for binary trees, SIAM J. comput., 30, 5, 1385-1404, (2000) · Zbl 0976.68081  T. Gagie, S.J. Puglisi, A. Turpin, Range quantile queries: another virtue of wavelet trees, in: International Conference on String Processing and Information Retrieval, 2009, pp. 1-6.  R. Grossi, A. Gupta, J.S. Vitter, High-order entropy-compressed text indexes, in: ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 841-850. · Zbl 1092.68584  Hagerup, T., Parallel preprocessing for path queries without concurrent Reading, Inform. and comput., 158, 1, 18-28, (2000) · Zbl 1046.68979  Harel, D.; Tarjan, R.E., Fast algorithms for finding nearest common ancestors, SIAM J. comput., 13, 2, 338-355, (1984) · Zbl 0535.68022  M. He, J.I. Munro, G. Zhou, Path queries in weighted trees, in: International Symposium on Algorithms and Computation, 2011, pp. 140-149. · Zbl 1350.68073  M. He, J.I. Munro, G. Zhou, Succinct data structures for path queries, in: European Symposium on Algorithms, 2012.  W.-K. Hon, R. Shah, J.S. Vitter, Ordered pattern matching: towards full-text retrieval, Purdue University Tech. Rept. CSD TR 06-008, 2006.  G. Jacobson, Space-efficient static trees and graphs, in: IEEE Symposium on Foundations of Computer Science, 1984, pp. 549-554.  J. Jansson, K. Sadakane, W.-K. Sung, Ultra-succinct representation of ordered trees, in: ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 575-584. · Zbl 1302.68100  Krizanc, D.; Morin, P.; Smid, M.H.M., Range mode and range Median queries on lists and trees, Nordic J. comput., 12, 1, 1-17, (2005) · Zbl 1083.68028  Lu, H.-I.; Yeh, C.-C., Balanced parentheses strike back, ACM trans. algorithms, 4, 3, (2008), Article No. 28  V. Mäkinen, G. Navarro, Position-restricted substring searching, in: Latin American Symposium on Theoretical Informatics, 2006, pp. 703-714. · Zbl 1145.68392  Munro, J.I.; Raman, V., Succinct representation of balanced parentheses and static trees, SIAM J. comput., 31, 3, 762-776, (2001) · Zbl 1017.68037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.