Improved Submatrix Maximum Queries in Monge Matrices

Pawel Gawrychowski, Shay Mozes, Oren Weimann

We present efficient data structures for submatrix maximum queries in Monge matrices and Monge partial matrices. For $n\times n$ Monge matrices, we give a data structure that requi…