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

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 subarray. For word size $Θ(\log n)$, any cell-probe data structure answering queries in time $t$ requires $2n-1.5\log n+n