As part of a solution to an earlier question, I am interested in the following problem.

I have a 2-D matrix $M$. I want to preprocess it in linear time so that I can answer queries of the following form in constant time:

Given $i_1 \leq i_2$ and $j_1 \leq j_2$, what is the minimum of $\{ M_{ij} : i_1 \leq i \leq i_2, j_1 \leq j \leq j_2 \}$?

Such a method is described in On Space Efficient Two Dimensional Range Minimum Data Structures, but I am unable to understand it.

  • 2
    $\begingroup$ Which part don't you understand? Interpreting the whole paper would be too broad to answer. $\endgroup$ – xskxzr Feb 12 '19 at 14:09
  • $\begingroup$ imagine there are n queries. In each query, you are given the submatrix(it can be any submatrix) you need to effectively return the position of the minimum number in that submatrix.And all numbers are unique. $\endgroup$ – Manoharsinh Rana Feb 12 '19 at 16:20
  • $\begingroup$ @xskxzr they are doing some preprocessing. $\endgroup$ – Manoharsinh Rana Feb 12 '19 at 16:58
  • 1
    $\begingroup$ For your application it suffices to support one-dimensional minimum range queries, for which much simpler data structures exist. See my updated answer to your original question. $\endgroup$ – Yuval Filmus Feb 12 '19 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.