Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries

Seungbum Jo, Geunho Kim

Given an array of size $n$ from a total order, we consider the problem of constructing a data structure that supports various queries (range minimum/maximum queries with their vari…