<p>So, you are interested in range queries in the "dense case" (an array) as opposed to the case most frequently studied in theory (arbitrary points in space).</p>

<p>The RMQ problem is easier than the semigroup sum problem, and no $\alpha$ is needed. The most recent result I know is: <a href="http://www.siam.org/proceedings/soda/2010/SODA10_014_yuanh.pdf" rel="nofollow">Hao Yuan, Mikhail J. Atallah: Data Structures for Range Minimum Queries in Multidimensional Arrays, SODA 2010</a></p>

<p>The semigroup sum problem is mainly of theoretical interest, in my opinion (what is a natural semigroup beyond max?). This explains why the Chazelle-Rosenberg paper does not have a lot of citations.</p>

CC BY-SA 2.5
2010-09-30T17:12:25.927Z
added a link to the paper. But Mihai, wasn't he asking about range max ? you can fix this for integers by flipping signs or subtracting, but without inverses can that be done ?
Suresh Venkat
CC BY-SA 2.5
2010-10-01T02:51:36.730Z
"what is a natural semigroup beyond max?" There are tons. Free semigroups (list concatenation). Operator/matrix semigroups. Lattices wrt join/meet. Saturated semigroups other than min/max semigroups (e.g. Tony Morris's [validation semigroup](http://blog.tmorris.net/automated-validation-with-applicatives-and-semigroups-for-sanjiv/)). Maybe not useful in the context of the semigroup sum problem, but definitely useful in general.
Per Vognsen
CC BY-SA 2.5
2010-10-08T09:14:25.303Z
Accepted the answer, thank you! Really looks like there are no interesting semigroups beyond max to make RSQ problem very interesting. If somebody knows any examples, I would be interested to know.
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-09-30T17:02:21.880Z
2010-09-30T17:10:45.460Z
2010-09-30T17:10:45.460Z
Mihai
<blockquote>
  <p><strong>Problem:</strong> 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).</p>
</blockquote>

<p>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?</p>

<p>I'm interested in it because looks like the best asymptotics for both RMQ and RSQ was achieved in <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.7405&amp;rep=rep1&amp;type=pdf" rel="nofollow">this</a> 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. </p>

CC BY-SA 2.5
2010-09-30T07:05:09.043Z
you should probably explain the acronyms. Is RMQ range-minimum and RSQ range-sum ?
Suresh Venkat
CC BY-SA 2.5
2010-09-30T16:49:49.293Z
this is the kind of edit I had in mind.
Suresh Venkat
CC BY-SA 2.5
2010-09-30T18:32:21.633Z
@Suresh Thanks for a comment, added the problem statement.
Grigory Yaroslavtsev
<ds.algorithms><reference-request><ds.data-structures><range-searching>
Offline multidimensional RMQ/RSQ in query model
Grigory Yaroslavtsev
# Offline multidimensional RMQ/RSQ in query model

(Asked by: username_0 on 2010-09-30)

> **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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.7405&rep=rep1&type=pdf) 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.

**Tags:** ds.algorithms, reference-request, ds.data-structures, range-searching
> **Comments:**
> **username_1**: you should probably explain the acronyms. Is RMQ range-minimum and RSQ range-sum ?  
> **username_1**: this is the kind of edit I had in mind.  
> **username_0**: @Suresh Thanks for a comment, added the problem statement.  

---

## 1 answers

### Answer by username_2 on 2010-09-30. Score: 6 | Accepted answer

So, you are interested in range queries in the "dense case" (an array) as opposed to the case most frequently studied in theory (arbitrary points in space).

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](http://www.siam.org/proceedings/soda/2010/SODA10_014_yuanh.pdf)

The semigroup sum problem is mainly of theoretical interest, in my opinion (what is a natural semigroup beyond max?). This explains why the Chazelle-Rosenberg paper does not have a lot of citations.

> **Comments:**
> **username_1**: added a link to the paper. But Mihai, wasn't he asking about range max ? you can fix this for integers by flipping signs or subtracting, but without inverses can that be done ?  
> **username_3**: "what is a natural semigroup beyond max?" There are tons. Free semigroups (list concatenation). Operator/matrix semigroups. Lattices wrt join/meet. Saturated semigroups other than min/max semigroups (e.g. Tony Morris's [validation semigroup](http://blog.tmorris.net/automated-validation-with-applicatives-and-semigroups-for-sanjiv/)). Maybe not useful in the context of the semigroup sum problem, but definitely useful in general.  
> **username_0**: Accepted the answer, thank you! Really looks like there are no interesting semigroups beyond max to make RSQ problem very interesting. If somebody knows any examples, I would be interested to know.  

---

