Given an array of n elements from a total order, we propose encodings that support various range queries (range minimum, range maximum and their variants), and previous and next smaller/larger value queries. When query time is not of concern, we obtain a 4.088n + o(n)-bit encoding that supports all these queries. For the case when we need to support all these queries in constant time, we give an encoding that takes 4.585n + o(n) bits, where n is the length of input array. We first extend the original DFUDS [Algorithmica, 2005] encoding of the colored 2d-Min (Max) heap that supports the queries in constant time. Then, we combine the extended DFUDS of 2d-Min heap and 2d-Max heap using the Min-Max encoding of Gawrychowski and Nicholson [arXiv, 2014] with some modifications. We also obtain encodings that take lesser space and support a subset of these queries.
展开▼
