Lower bound for succinct range minimum query

Given an integer array A [1. n ], the Range Minimum Query problem (RMQ) asks to preprocess A into a data structure, supporting RMQ queries: given a , b ∈ [1, n ], return the index i ∈[ a , b ] that minimizes A [ i ], i.e., argmin i ∈[ a , b ] A [ i ]. This problem has a classic solution using O ( n ) space and O (1) query time by Gabow, Bentley, Tarjan (STOC, 1984) and Harel, Tarjan (SICOMP, 1984). The best known data structure by Fischer, Heun (SICOMP, 2011) and Navarro, Sadakane (TALG, 2014) uses 2 n + n /(log n / t ) t +Õ( n 3/4 ) bits and answers queries in O ( t ) time, assuming the word-size is w =Θ(log n ). In particular, it uses 2 n + n / poly log n bits of space as long as the query time is a constant. In this paper, we prove the first lower bound for this problem, showing that 2 n + n / poly log n space is necessary for constant query time. In general, we show that if the data structure has query time O ( t ), then it must use at least 2 n + n /(log n ) Õ( t 2 ) space, in the cell-probe model with word-size w =Θ(log n ).

Authors

• Mingmou Liu
• Huacheng Yu

Keywords

• cell-probe complexity
• data structure
• lower bound
• range minimum query