I will present (parts) of the following paper which appeared in last years SODA.
If time permits I will mention some possibilities for improvements.
Title: Submatrix Maximum Queries in Monge Matrices and Monge Partial Matrices, and Their Applications.
Authors: Haim Kaplan, Shay Mozes, Yahav Nussbaum and Micha Sharir.
Reference: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 338-355.