Space-efficient data structure for next/previous larger/smaller value queries (Q6932710)

The article presents a new, space-efficient encoding data structure designed to support various range and value queries on an array of size \(n\). The key focus is on achieving a balance between minimal space usage and efficient query time within the encoding model, where queries must be answered without access to the original input array.\N\NThe proposed data structure combines the Balanced Parenthesis (BP) sequences of the colored 2d-min heap and 2d-max heap of the input array, utilizing \((3.701n + o(n))\) bits for general arrays. This matches the current best theoretical upper bound [\textit{D. Tsur}, Inf. Process. Lett. 145, 39--43 (2019; Zbl 1446.68047)], but improves upon it by providing efficient query support, which previous models lacked. Furthermore, the space requirement can be reduced to \((3.585n + o(n))\) bits if the array does not contain two consecutive equal elements. While some previous models (e.g., [\textit{J. Fischer} and \textit{V. Heun}, SIAM J. Comput. 40, No. 2, 465--492 (2011; Zbl 1222.05024)]) offer \(O(1)\) query time, they often require significantly more space (up to \(5.08n\) bits). The authors' structure is notably more space-efficient, although with a slightly slower query time for specific operations like \(q\)-th minimum or next smaller value.\N\NIn conclusion, the paper represents a significant advancement in succinct data structures. It successfully matches the best-known space bounds while ensuring that essential range and relative value queries are performed in near-constant time, making it a valuable contribution to the field.