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.