# Offline multidimensional RMQ/RSQ in query model

Problem: In the multidimensional range Max/Sum query problem (RMQ/RSQ) you are given a $d$-dimensional array with $n$ elements, and given a $d$-dimensional box, you wish to determine the max/sum of all elements in the range (if the elements are from semigroup, they have no inverses).

What is the state-of-art best algorithm for offline multidimensional RMQ/RSQ in query model (preprocessing of data allowed in offline, queries asked online)? Is there any gap between RMQ and RSQ in multidimensional case? What theoretical/practical interest does this problem have, if any?

I'm interested in it because looks like the best asymptotics for both RMQ and RSQ was achieved in this paper by Chazelle and Rosenberg in 1989, which was not cited a lot, though the problem looks very natural and interesting. By best asymptotics I mean $O(\alpha^d(m,n))$ query time, where $m$ is the amount of storage available per element, $d$ --- number of dimensions of the array, $\alpha$ --- inverse Ackerman function, $n$ --- number of entries in the array. I suspect that this is mainly because this paper is not very readable in the part where it describes the construction, so implementation of this approach is complicated. So a simpler description of a data structure with the same asymptotics is also very welcome.

• you should probably explain the acronyms. Is RMQ range-minimum and RSQ range-sum ? – Suresh Venkat Sep 30 '10 at 7:05
• this is the kind of edit I had in mind. – Suresh Venkat Sep 30 '10 at 16:49
• @Suresh Thanks for a comment, added the problem statement. – Grigory Yaroslavtsev Sep 30 '10 at 18:32

The RMQ problem is easier than the semigroup sum problem, and no $\alpha$ is needed. The most recent result I know is: Hao Yuan, Mikhail J. Atallah: Data Structures for Range Minimum Queries in Multidimensional Arrays, SODA 2010