Optimal Succinctness for Range Minimum Queries

Details Optimal Succinctness for Range Minimum Queries Optimal Succinctness for Range Minimum Queries

2008-12-15

arxiv.org/abs/0812.2775v3

Computer Science

Data Structures and Algorithms

12 pages; to appear in Proc. LATIN'10

Scientific paper

For a static array A of n ordered objects, a range minimum query asks for the position of the minimum between two specified array indices. We show how to preprocess A into a scheme of size 2n+o(n) bits that allows to answer range minimum queries on A in constant time. This space is asymptotically optimal in the important setting where access to A is not permitted after the preprocessing step. Our scheme can be computed in linear time, using only n + o(n) additional bits at construction time. In interesting by-product is that we also improve on LCA-computation in BPS- or DFUDS-encoded trees.

Affiliated with

Also associated with

No associations

Rating

Optimal Succinctness for Range Minimum Queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Succinctness for Range Minimum Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Succinctness for Range Minimum Queries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-348969