Nearly Tight Lower Bound for Range Minimum Query via Probe-by-Probe Information Accounting

Mingmou Liu

We prove a nearly tight lower bound for succinct Range Minimum Query (RMQ) on an array of $n$ distinct integers. A query returns the position of the smallest entry in a specified s…