Range Median of Minima Queries, Super-Cartesian Trees, and Text Indexing.
Johannes Fischer, Volker Heun · 2008
A Range Minimum Query asks for the position of a minimal element between two specified array-indices. We consider a natural extension of this, where our further constraint is that if the minimum in a query interval is not unique, then the query should return an approximation of the median position among all positions that attain this minimum. We present a succinct preprocessing scheme using only about 2.54 n + o(n) bits in addition to the static input array, such that subsequent “range median of minima queries” can be answered in constant time. This data structure can be constructed in linear time, and only o(n) additional bits are needed at construction time. We introduce several new combinatorial concepts such as Super-Cartesian Trees and Super-Ballot Numbers, which we believe will have other interesting applications in the future. We stress the importance of our result by giving two applications in text indexing; in particular, we show that our ideas are needed for fast construction of one component in Compressed Suffix Trees [19], a versatile tool for numerous tasks in text processing, and that they can be used for fast pattern matching in (compressed) suffix arrays [14].