Range mode and range median queries on lists and trees. (English) Zbl 1205.68130

Krizanc, Danny; Morin, Pat; Smid, Michiel

Ibaraki, Toshihide (ed.) et al., Algorithms and computation. 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15–17, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20695-7/pbk). Lect. Notes Comput. Sci. 2906, 517-526 (2003).

Summary: We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes \(u\) and \(v\) we can answer queries of the form: What is the mode or median label in the sequence of labels on the path from \(u\) to \(v\).
For the entire collection see [Zbl 1029.00053].

MSC:

68P05

Data structures