# Minimum number queries on matrix

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.

• Which part don't you understand? Interpreting the whole paper would be too broad to answer. – xskxzr Feb 12 at 14:09
• 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. – Manoharsinh Rana Feb 12 at 16:20
• @xskxzr I did not understand,How can you find minimum number in O(1) complexity. – Manoharsinh Rana Feb 12 at 16:21
• @xskxzr they are doing some preprocessing. – Manoharsinh Rana Feb 12 at 16:58
• 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. – Yuval Filmus Feb 12 at 17:35