Submatrix Maximum Queries in Monge Matrices
are Equivalent to Predecessor Search?
Paweł Gawrychowski1 , Shay Mozes2?? , and Oren Weimann3??

arXiv:1502.07663v3 [cs.DS] 25 Dec 2017

1

University of Wrocław, gawry@cs.uni.wroc.pl
2
IDC Herzliya, smozes@idc.ac.il
3
University of Haifa, oren@cs.haifa.ac.il

Abstract. We present an optimal data structure for submatrix maximum queries in n×n Monge matrices. Our result is a two-way reduction showing that the problem is equivalent to the classical predecessor
problem in a universe of polynomial size. This gives a data structure of O(n) space that answers submatrix maximum queries in O(log log n) time, as well as a matching lower bound, showing that O(log log n)
query-time is optimal for any data structure of size O(n polylog(n)). Our result settles the problem,
improving on the O(log2 n) query-time in SODA’12, and on the O(log n) query-time in ICALP’14.
In addition, we show that partial Monge matrices can be handled in the same bounds as full Monge matrices. In both previous results, partial Monge matrices incurred additional inverse-Ackermann factors.

1

Introduction

Data structures for range queries and for predecessor queries are among the most studied data structures in
computer science. Given an n × n matrix M , a range maximum (also called submatrix maximum) data structure can report the maximum entry in any query submatrix (a set of consecutive rows and a set of consecutive
columns) of M . Given a set S ⊆ [0, U ) of n integers from a polynomial universe U , a predecessor data structure can report the predecessor (and successor) in S of any query integer x ∈ [0, U ). In this paper, we prove
that these two seemingly unrelated problems are in fact equivalent when the matrix M is a Monge matrix.
Range maximum queries. A long line of research over the last three decades including [4,11,12,15,24]
achieved range maximum data structures of Õ(n2 ) space and Õ(1) query time4 , culminating with the
O(n2 )-space O(1)-query data structure of Yuan and Atallah [24]. In general matrices, this is optimal since
representing the input matrix already requires Θ(n2 ) space. In fact, reducing the additional space to O(n2 /c)
is known to incur an Ω(c) query-time [6] and such tradeoffs can indeed be achieved for any value of c [5,6].
However, in many applications, the matrix M is not stored explicitly but any entry of M can be computed
when needed in O(1) time. One such case is when the matrix M is sparse, i.e., has N = o(n2 ) nonzero entries.
In this case the problem is known in computational geometry as the orthogonal range searching problem on
the n × n grid. In this case as well, various data structures with Õ(N )-space and Õ(1)-query appear in a long
history of results including [3,9,10,13,15]. For a survey on orthogonal range searching see [22]. Another case
where the additional space can be made o(n2 ) (and in fact even O(n)) is when the matrix is a Monge matrix.
Range maximum queries in Monge matrices. A matrix M is Monge if for any pair of rows i < j and
columns k < ` we have that M [i, k] + M [j, `] ≥ M [i, `] + M [j, k].5 A matrix M is Totally Monotone (or
TM) if for any pair of rows i < j and columns k < ` we have that if M [i, k] ≤ M [j, k] then M [i, `] ≤ M [j, `].
Notice that the Monge property implies total monotonicity but the converse is not true. Whenever possible,
we state our results for the more general class of TM matrices. Throughout the paper we use a top-down
?
??
4
5

This paper is based on two preliminary papers that appeared in ICALP 2014 and ICALP 2015.
Mozes and Weimann supported in part by Israel Science Foundation grant 794/13.
The Õ(·) notation hides polylogarithmic factors in n.
Monge matrices are often defined with a ≤ (rather than ≥) in the condition. Our results apply to both definitions,
as well as to minimum (rather than maximum) queries.

and left-to-right ordering of the elements of a matrix. We say that M [i, k] is above M [j, `] if i < j, and to
the left of M [j, `] if k < `.
Submatrix maximum queries on Monge matrices have various important applications in combinatorial
optimization and computational geometry such as problems involving distances in the plane, and in problems
on convex n-gons. See [7] for a survey on Monge matrices and their uses in combinatorial optimization.
Submatrix maximum queries on Monge matrices are used in algorithms that efficiently find the largest empty
rectangle containing a query point, in dynamic distance oracles for planar graphs, and in algorithms for
maximum flow in planar graphs. See [18] for more details on the history of this problem and its applications.
Given an n × n Monge matrix M it is possible to obtain compact data structures of only Õ(n) space that
can answer submatrix maximum queries in Õ(1) time. The first such data structure was given by Kaplan,
Mozes, Nussbaum and Sharir [18]. They presented an O(n log n)-space data structure with O(log2 n) query
time. This was improved in [17] to O(n) space and O(log n) query time.
Breakpoints and Partial Monge matrices. Given an m × n Monge matrix M , let r(c) be the row
containing the maximum element in the c-th column of M . It is easy to verify that the r(·) values are
monotone, i.e., r(1) ≤ r(2) ≤ . . . ≤ r(n). Columns c such that r(c − 1) < r(c) (or c = 1) are called the
breakpoints of M . A Monge matrix consisting of m < n rows has O(m) breakpoints, which can be found in
O(n) time using the SMAWK algorithm [2] (total monotonicity suffices for SMAWK).
Some applications involve partial Monge matrices rather than full Monge matrices. A partial matrix is a
matrix where some of the entries are undefined, but the defined entries in each row and in each column are
contiguous. A partial Monge matrix is a partial matrix in which the Monge inequality is satisfied whenever
all four involved entries are defined. The total number of breakpoints in a partial Monge matrix is still
O(m) (as we show in Section 5), and they can be found in O(n · α(n)) time6 using an algorithm of Klawe
and Kleitman [19]. This was used in [17,18] to extend their solutions to partial Monge matrices at the cost
of an additional α(n) factor to the query time.7
Our results. In this paper, we fully resolve the submatrix maximum query problem in n × n Monge
matrices by presenting a data structure of O(n) space and O(log log n) query time. Consequently, we obtain
an improved query time for other applications such as finding the largest empty rectangle containing a query
point. We compliment our upper bound with a matching lower bound, showing that O(log log n) query-time is
optimal for any data structure of size O(n polylog(n)). Implicit in our upper and lower bound is an equivalence
between the predecessor problem in a universe of polynomial size and the range maximum query problem in
Monge matrices. The upper bound essentially reduces a submatrix query to a constant number of predecessor
problems, and vice versa, the lower bound reduces the predecessor problem to a submatrix query problem.
In fact, the lower bound holds even for the more restricted case where the submatrix query is a subcolumn.
Finally, we extend our result to partial Monge matrices with the exact same bounds (i.e., O(n) space
and O(log log n) query time). Our result is the first to achieve such extension with no overhead.
Techniques. Let M be an n × n Monge matrix8 . Consider a full binary tree T whose leaves are the rows of
M . Let Mu be the submatrix of M composed of all rows (i.e., leaves) in the subtree of a node u in T . Both
existing data structures for submatrix maximum queries [17,18] store, for each node u in T a data structure
Du . The goal of Du is to answer submatrix maximum queries that include an arbitrary interval of columns
and exactly all rows of Mu . This way, an arbitrary query is covered in [17,18] by querying the Du structures
of O(log n) canonical nodes of T . An Ω(log n) bound is thus inherent for any solution that examines the
canonical nodes. We overcome this obstacle by designing a stronger data structure Du . Namely, one that
supports queries that include an arbitrary interval of columns and a prefix of rows or a suffix of rows of Mu .
This way, an arbitrary query can be covered by just two Du s. The idea behind the new design is to efficiently
encode the changes in column maxima as we add rows to Mu one by one. Retrieving this information is done
using weighted ancestor search and range maximum queries on trees. This is a novel use of these techniques.
6
7
8

Here α(n) is the inverse-Ackermann function.
In [18], there was also an additional log n factor to the space.
We consider m × n matrices, but for simplicity we sometimes state the results for n × n matrices.

2

For our lower bound, we show that for any set of n integers S ⊆ [0, n2 ) there exists an n × n Monge
matrix M such that the predecessor of x in S can be found with submatrix maximum queries on M . The
predecessor lower bound of Pǎtraşcu and Thorup [23] then implies that O(n polylog(n)) space requires
Ω(log log n) query time. We overcome two technical difficulties here: First, M should be Monge. Second,
there must be an O(n polylog(n))-size representation of M which can retrieve any entry M [i, j] in O(1) time.
Finally, for handling partial Monge matrices, and unlike previous solutions for this case, we do not
directly adapt the solution for the full Monge case to partial Monge matrices. Instead we decompose the
partial Monge matrix into many full Monge matrices, that can be preprocessed to be queried cumulatively in
an efficient way. This requires significant technical work and careful use of the structure of the decomposition.
Computational model. We assume the standard word RAM model with word size Ω(log n). However,
this is just an internal assumption and the elements of the matrix M are only accessed through a comparison
oracle, that is, we only assume that we are able to check in constant time if M [i, j] ≤ M [i0 , j 0 ] and no
arithmetical manipulation on the elements of M is performed.
Roadmap. In Section 2 we present an O(n log n)-space data structure for Monge matrices that answers
submatrix maximum queries in O(log log n) time. In Section 3 we reduce the space to O(n). Our lower
bound is given in Section 4, and the extension to partial Monge matrices in Section 5.

2

Data structure for Monge matrices

Our goal in this section is to construct, for a given m × n Monge matrix M , a data structure of size
O(m log n) that answers submatrix maximum queries in O(log log n) time. In Section 3 we show how to
reduce the space from O(n log n) to O(n) when m = n. We will actually show a stronger result, namely the
structure allows us to reduce in O(1) time a submatrix maximum query into O(1) predecessor queries on a
set consisting of n integers from a polynomial universe.
We denote by pred(m, n) the complexity of a predecessor query on a set of m integers from
a universe {0, . . . , n − 1}. It is well known that there are O(m)-space data structures achieving
pred(m, n) = min{O(log m), O(log log n)}.
Recall that a submatrix maximum query returns the maximum M [i, j] over all i ∈ [i0 , i1 ] and j ∈ [j0 , j1 ]
for given i0 ≤ i1 and j0 ≤ j1 . We start by answering the easier subcolumn maximum queries within these
space and time bounds. That is, finding the maximum M [i, j] over all i ∈ [i0 , i1 ] for given i0 ≤ i1 and j.
We construct a full binary tree T over the rows of M . Every leaf of the tree corresponds to a single row
of M , and every inner node corresponds to the range of rows in its subtree. To find the maximum M [i, j]
over all i ∈ [i0 , i1 ] for given i0 ≤ i1 and j, we first locate the lowest common ancestor (lca) u of the leaves
corresponding to i0 and i1 in the tree. Then we decompose the query into two parts: one fully within the
range of rows M` of the left child of u, and one fully within the range of rows Mr of the right child of u.
The former ends at the last row of M` and the latter starts at the first row of Mr . We equip every node
with two data structures supporting such simpler subcolumn maximum queries. Because of symmetry (if M
is Monge, so is M 0 , where M 0 [i, j] = M [n + 1 − i, n + 1 − j]) it suffices to show how to answer subcolumn
maximum queries starting at the first row.
Lemma 1. Given an m × n TM matrix M , a data structure of size O(m) can be constructed in O(m log n)
time to answer in O(pred(m, n)) time subcolumn maximum queries starting at the first row of M .
Proof. Consider queries spanning an entire column c of M . To answer such a query, we only need to find
the corresponding r(c). If we store the breakpoints of M in a predecessor structure, where every breakpoint
c links to its corresponding value of r(c), a query can be answered with a single predecessor search. More
precisely, to determine the maximum in the c-th column of M , we locate the largest breakpoint c0 ≤ c,
and then set r(c) = r(c0 ). Hence we can construct a data structure of size O(m) to answer entire column
maximum queries in O(pred(m, n)) time.
3

Let Mi be a TM matrix consisting of the first i rows of M . By applying the above reasoning to every Mi
separately, we immediately get a structure of size O(m2 ) answering subcolumn maximum queries starting
at the first row of M in O(pred(m, n)) time. We want to improve on this by utilizing the dependency of the
structures constructed for different i’s. Observe that the list of breakpoints of Mi+1 is a prefix of the list of
breakpoints of Mi to which we append at most one new element. In other words, if the breakpoints of Mi are
stored on a stack, we need to pop zero or more elements and push at most one new element to represent the
breakpoints of Mi+1 . Consequently, instead of storing a separate list for every Mi , we can succinctly describe
the content of all stacks with a single tree T on at most m + 1 nodes. For every i, we store a pointer to a node
s(i) ∈ T , such that the ancestors of s(i) (except for the root) are exactly the breakpoints of Mi . Whenever we
pop an element from the current stack, we move to the parent of the current node, and whenever we push an
element, we create a new node and make it a child of the current node. Initially, the tree consists of just the
root. Every node is labelled with a column number and by construction these numbers are strictly increasing
on any path starting at the root (the root is labelled with −∞). Therefore, a predecessor search for j among
the breakpoints of Mi reduces to finding the leafmost ancestor of s(i) whose label is at most j. This is known as
the weighted ancestor problem. Weighted ancestor queries on a tree of size O(m) are equivalent to predecessor
searching on a number of sets of O(m) total size [20],9 achieving the claimed space and query time bounds.
To finish the proof, we need to bound the construction time. The bottleneck is constructing the tree
T . Let c1 < c2 < . . . < ck for some k ≤ i be the breakpoints of Mi . As long as M [i + 1, ck ] ≥ M [r(ck ), ck ]
we decrease k by one, i.e., remove the last breakpoint. This process is repeated O(m) times in total.
If k = 0 we create a new breakpoint c1 = 1. If k ≥ 1 and M [i + 1, ck ] < M [r(ck ), ck ], we check if
M [i + 1, n] ≥ M [r(ck ), n]. If so, we need to create a new breakpoint. To this end, we need to find the smallest
j such that M [i+1, j] ≥ M [r(ck ), j]. This can be done in O(log n) using binary search. Consequently, T can be
constructed in O(m log n) time. Then augmenting it with a weighted ancestor structure takes O(m) time. t
u
We apply Lemma 1 twice to every node of the full version tree T . Once for subcolumn maximum queries
starting at the first row and once for queries ending at the last row. Since the total size of all structures
at the same level of the tree is O(m), the total size of our subcolumn maximum data structure becomes
O(m log m), and it can be constructed in O(m log m log n) time to answer queries in O(pred(m, n)) time.
Hence we have proved the following.
Theorem 1. Given an m × n TM matrix M , a data structure of size O(m log m) can be constructed in
O(m log m log n) time to answer subcolumn maximum queries in O(pred(m, n)) time.
By symmetry (a transpose of a Monge matrix is Monge) we can answer subrow maximum queries (where
the query is a single row and a range of columns) in O(pred(n, m)) time. We are now ready to tackle general
submatrix maximum queries.
At a high level, the idea is identical to the one used for subcolumn maximum queries: we construct a full
binary tree T over the rows of M , where every node corresponds to a range of rows. To find maximum
M [i, j] over all i ∈ [i0 , i1 ] and j ∈ [j0 , j1 ] for given i0 ≤ i1 and j0 ≤ j1 , we locate the lowest common
ancestor of the leaves corresponding to i0 and i1 and decompose the query into two parts, the former ending
at the last row of M` and the latter starting at the first row of Mr . Every node is equipped with two data
structures allowing us to answer submatrix maximum queries starting at the first row or ending at the last
row. As before, it suffices to show how to answer submatrix maximum queries starting at the first row.
Lemma 2. Given an m × n Monge matrix M , and a data structure that answers subrow maximum
queries on M in O(pred(n, m)) time, one can construct in O(m log m) time a data structure consuming
O(m) additional space, that answers submatrix maximum queries starting at the first row of M in
O(pred(m, n) + pred(n, m)) time.
9

The reduction described in [20] needs O(log∗ m) additional time and (adaptively) queries two sets. The additional
time is required to reduce the total size of the sets to O(m), which is done by recursively decomposing the tree.
However, this recursive decomposition can be avoided using atomic heaps as explained in Lemma 11 of [16]. Then in
O(1) additional time we are able to reduce a weighted ancestor query to a single predecessor query in one of the sets.

4

Proof. We extend the proof of Lemma 1. Let c1 < c2 < . . . < ck be the breakpoints of M stored in a
predecessor structure. For every i ≥ 2 we precompute and store the value
mi =

max

j∈[ci−1 ,ci )

M [r(ci−1 ), j].

These values are augmented with a (one dimensional) range maximum query data structure. To begin with,
consider a submatrix maximum query starting at the first row of M and ending at the last row of M , i.e.,
we need to calculate the maximum M [i, j] over all i ∈ [1, m] and j ∈ [j0 , j1 ]. We find in O(pred(m, n)) the
successor of j0 , denoted ci , and the predecessor of j1 , denoted ci0 . There are three possibilities:
1. The maximum is reached for j ∈ [j0 , ci ),
2. The maximum is reached for j ∈ [ci , ci0 ),
3. The maximum is reached for j ∈ [ci0 , j1 ).
The first and the third possibilities can be calculated with subrow maximum queries in O(pred(n, m))
time, because both ranges span an interval of columns and a single row. The second possibility can be
calculated with a range maximum query on the range (i, i0 ] over the precomputed values mi associated to
the breakpoints. Consequently, we can construct a data structure of size O(m) to answer such submatrix
maximum queries in O(pred(m, n) + pred(n, m)) time.
The above solution can be generalized to queries that start at the first row of M but do not necessarily
end at the last row of M . This is done by considering the Monge matrices Mi consisting of the first i rows
of M . For every such matrix, we need a predecessor structure storing all of its breakpoints, and additionally
a range maximum structure over their associated values mi . Hence now we need to construct a similar tree
T as in Lemma 1 on O(m) nodes, but now every node has both a weight and a value. The weight of a node
is the column number of the corresponding breakpoint ck , and the value is its mk (or undefined if k = 1).
As in Lemma 1, the breakpoints of Mi are exactly the ancestors of the node s(i). Note that every mk is
defined in terms of ck−1 and ck , but this is not a problem because the predecessor of a breakpoint does
not change during the whole construction. We maintain a weighted ancestor structure using the weights (in
order to find ci and ci0 in O(pred(m, n)) time), and a generalized range maximum structure using the values.
A generalized range maximum structure of a tree T , given two query nodes u and v, returns the maximum
value on the unique u-to-v path in T . It can be implemented in O(m) space and O(1) query time after
O(m log m) preprocessing [12] once we have the values. The values can be computed with subrow maximum
queries in O(m · pred(n, m)) = O(m log m) total time.
t
u
By applying Lemma 2 twice to every node of the full binary tree T , we construct in O(m log2 m) time
a data structure of size O(m log m) to answer submatrix maximum queries in O(pred(m, n) + pred(n, m))
time. In order to apply Lemma 2 to a node of T we need a subrow maximum query data structure for the
corresponding rows of the matrix M . Note, however, that a single subrow maximum query data structure
for M can be used for all nodes of T . We thus obtained the following theorem.
Theorem 2. Given an m × n Monge matrix M , and a data structure answering subrow maximum queries
on M in O(pred(n, m)) time, one can construct in O(m log2 m) time a data structure taking O(m log m)
additional space, that answers submatrix maximum queries on M in O(pred(m, n) + pred(n, m)) time.
By combining Theorem 1 with Theorem 2, given an n × n Monge matrix M , a data structure of size
O(n log n) can be constructed in O(n log2 n) time to answer submatrix maximum queries in O(pred(n, n))
time.

3

Obtaining linear space

In this section we show how to decrease the space of the data structure presented in Section 2 to be linear.
We extend the idea developed in our previous paper [17]. The previous linear space solution was based on
partitioning the matrix M into n/x matrices M1 , M2 , . . . , Mn/x , where each Mi is a slice of M consisting
of x = log n consecutive rows. Then, instead of working with the matrix M , we worked with the (n/x) × n
matrix M 0 , where M 0 [i, j] is the maximum entry in the j-th column of Mi .
5

Subcolumn queries. Consider a subcolumn query. Suppose the query is entirely contained in some Mi .
This means it spans less than x = log n rows. In [17], since the desired query time was O(log n), a query
simply inspected all elements of the subcolumn. In our case however, since the desired query time is only
O(log log n), we apply the above partitioning scheme twice. We explain this now.
We start with the following lemma, that provides an efficient data structure for queries consisting of a
single column and all rows in rectangular matrices.
Lemma 3 (the micro data structure). Given an x × n TM matrix and r > 0, one can construct in
O(x log n/ log r) time, a data structure of size O(x) that given a query column can report the maximum entry
in the entire column in O(r + pred(x, n)) time.
Proof. Out of all n columns of the input matrix M , we will designate O(x) columns as special columns. For
each of these special columns we will eventually compute its maximum element. The first x special columns
of M are columns 1, n/x, 2n/x, 3n/x, . . . , n and are denoted j1 , . . . , jx .
Let X denote the x × x submatrix obtained by taking all x rows but only the x special columns j1 , . . . , jx .
It is easy to verify that X is TM. We can therefore run the SMAWK algorithm [2] on X in O(x) time and
obtain the column maxima of all special columns. Let r(j) denote the row containing the maximum element
in column j 10 Since M is TM, the r(j) values are monotonically non-decreasing. Consequently, r(j) of
a non-special column j must be between r(ji ) and r(ji+1 ) where ji < j and ji+1 > j are the two special
columns bracketing j (see Figure 1).
n

ji

m

x

xi

j

ji+1

r(ji )
Mi

r(ji+1 )

n/x

Fig. 1. An x×n matrix inside an m×n matrix. The black columns are the first x special columns. The (monotonically
non-decreasing) gray cells inside these special columns are the column maxima (i.e., the r(ji ) values of breakpoints
ji ). The maximum element of column j in the x × n matrix must be between r(ji ) and r(ji+1 ) (i.e., in matrix Mi ).

For every i, let xi = r(ji+1 ) − r(ji ). If xi ≤ r then no column between ji and ji+1 will ever be a special
column. When we will query such a column j we can simply check (at query-time) the r elements of j between
rows r(ji ) and r(ji+1 ) in O(r) time. If, however, xi > r, then we designate more special columns between
ji and ji+1 . This is done recursively on the xi × (n/x) matrix Mi composed of rows r(ji ), . . . , r(ji+1 ) and
columns ji , . . . , ji+1 . That is, we mark xi evenly-spread columns of Mi as special columns, and run SMAWK
in O(xi ) time on the xi × xi submatrix Xi obtained by taking all xi rows but only these xi special columns.
We continue recursively until either xi ≤ r or the number of columns in Mi is at most r. In the latter case,
before terminating, the recursive call runs SMAWK in O(xi + r) = O(xi ) time on the xi × r submatrix Xi
obtained by taking the xi rows and all columns of Mi (i.e., all columns of Mi will become special).
10

We assume that no elements of the matrix are equal. The ties are resolved lexicographically.

6

After the recursion terminates, every column j of M is either special (in which case we computed its maximum), or its maximum is known to be in one of at most r rows (these rows are specified by the r(·) values of
the two special columns bracketing j). Let s denote the total number of columns that are marked as special.
We claim that s = O(x log n/ log r). To see this, notice that the number of columns in every recursive call
decreases by a factor of at least r and so the recursion
depth is O(logr n) = O(log n/ log r). In every recursive
P
level, the number of added special columns is
xi over all x0i s in this level that are at least r. In every recursive level, this sum is bounded by 2x because each one of the x rows of M can appear in at most two Mi ’s
(as the last row of one and the first row of the other). Overall, we get 2x · O(log n/ log r) = O(x log n/ log r).
Notice that s = O(x log n/ log r) implies that the total time complexity of the above procedure is also
O(x log n/ log r). This is because whenever we run SMAWK on a y × y matrix it takes O(y) time and y new
columns are marked as special. To complete the construction, we go over the s special columns from left to
right in O(s) time and throw away (mark as non-special) any column whose r(·) value is the same as that
of the preceding special column. This way we are left with only O(x) special columns, and the difference
in r(·) between consecutive special columns is at least 1 and at most r. In fact, it is easy to maintain O(x)
(and not O(s)) space during the construction by only recursing on sub matrices Mi where xi > 1. We note
that when r = 1, the eventual special columns are exactly the set of breakpoints of the input matrix M .
The final data structure is a predecessor data structure that holds the O(x) special columns and their associated r(·) values. Upon query of some column j, we search in pred(x, n) time for the predecessor and successor
of j and obtain the two r(·) values. We then search for the maximum of column j by explicitly checking all the
(at most r) relevant rows of column j. The query time is therefore O(r + pred(x, n)) and the space O(x). t
u
In the case of x = O(log n), using atomic heaps [14] (which support predecessor searches in constant
time) we obtain the following corollary:
Corollary 1. Given an x × n TM matrix, a data structure of size O(x) can be constructed in O(x log n)
time to answer entire-column maximum queries in O(1) time, if x = O(log n).
It is possible to use Lemma 3 to obtain a subcolumn data structure with faster O(n log n/ log log n)
preprocessing time, at the cost of slower O(log n) query time (cf. [17, Lemma 2]). We next describe our new
subcolumn data structure, which uses the above corollary and two applications of the partitioning scheme.
Theorem 3. Given an m × n Monge matrix M , a data structure of size O(m) can be constructed in
O(m log n) time to answer subcolumn maximum queries in O(log log(n + m)) time.
Proof. We first partition M into m/x matrices M1 , M2 , . . . , Mm/x , where x = log m. Every Mi is a slice of
M consisting of x consecutive rows. Next, we partition every Mi into x/x0 matrices Mi,1 , Mi,2 , . . . , Mi,x0 ,
where x0 = log log m. Every Mi,j is a slice of Mi consisting of x0 consecutive rows (without loss of generality,
assume that x divides m and x0 divides x). Now we define a new (m/x) × n matrix M 0 , where M 0 [i, j] is the
maximum entry in the j-th column of Mi . Similarly, for every Mi we define a new (x/x0 ) × n matrix Mi0 ,
where Mi0 [j, k] is the maximum entry in the k-th column of Mi,j .
We apply Corollary 1 on every Mi and Mi,j in O(m log n) total time and O(m) total space, so that any
M 0 [i, j] or Mi0 [j, k] can be retrieved in O(1) time. Furthermore, it can be easily verified that M 0 and all Mi0 s
are also Monge. To prove this, it is enough to argue that if N is an 4 × 2 Monge matrix, the 2 × 2 matrix
N 0 created by partitioning N into two slices, each consisting of two rows, whose elements are the maxima
in every column of each slice, is also Monge. To this end, we need to compare:
N 0 [1, 1] + N 0 [2, 2] = max(N [1, 1], N [2, 1]) + max(N [3, 2], N [4, 2])
and
N 0 [1, 2] + N 0 [2, 1] = max(N [1, 2], N [2, 2]) + max(N [3, 1], N [4, 1]).
Let max(N [1, 2], N [2, 2]) = N [i, 2], where i ∈ {1, 2}, and similarly max(N [3, 1], N [4, 1]) = N [i0 , 1], where
i0 ∈ {3, 4}. Then
(N 0 [1, 1] + N 0 [2, 2]) − (N 0 [1, 2] + N 0 [2, 1]) ≥ (N [i, 1] + N [i0 , 2]) − (N [i, 2] + N [i0 , 1])
7

which is at least 0 because of N being Monge.
Therefore, because M 0 and all Mi0 are all Monge, and by Corollary 1 their entries can be accessed in O(1) time, we can apply Theorem 1 on M 0 and every Mi0 . The total construction time is
O((m/x) log(m/x) log n + (m/x)(x/x0 ) log(x/x0 ) log n) = O(m log n), and the total size of all structures
constructed so far is O((m/x) log(m/x) + (m/x)(x/x0 ) log(x/x0 )) = O(m).
Now consider a subcolumn maximum query. If the range of rows is fully within a single Mi,j , the query
can be answered naively in O(x0 ) = O(log log m) time. Otherwise, if the range of rows is fully within a single
Mi , the query can be decomposed into a prefix fully within some Mi,j , an infix corresponding to a range of
rows in Mi0 , and a suffix fully within some Mi,j 0 . The maximum in the prefix and the suffix can be computed
naively in O(x0 ) = O(log log m) time, and the maximum in the infix can be computed in O(log log n) time
using the structure constructed for Mi0 . Finally, if the range of rows starts inside some Mi and ends inside
another Mi0 , the query can be decomposed into two queries fully within Mi and Mi0 , respectively, which can
be processed in O(log log n) time as explained before, and an infix corresponding to a range of rows of M 0 .
The maximum in the infix can be computed in O(log log n) time using the structure constructed for M 0 . t
u
Submatrix queries. We are ready to present the final version of our data structure. It is based on two
applications of the partitioning scheme, and an additional trick of transposing the matrix.
Theorem 4. Given an n × n Monge matrix M , a data structure of size O(n) can be constructed in
O(n log n) time to answer submatrix maximum queries in O(log log n) time.
Proof. We partition M as described in the proof of Theorem 3, i.e., M is partitioned into n/x matrices
M1 , M2 , . . . , Mn/x , where x = log n, and every Mi is then partitioned into x/x0 matrices Mi,1 , Mi,2 , . . . , Mi,x0 ,
where x0 = log log n. Then we define smaller Monge matrices M 0 and Mi0 , and provide O(1) time access to
their entries with Corollary 1. We apply Theorem 3 to the transpose of M 0 to get a subrow maximum query
data structure for M 0 . This takes O(n) space and O(n log n) time. With this data structure we can apply
Theorem 2 on M 0 , which takes an additional O( logn n log logn n ) = O(n) space and O(n log n) time. We also
n
n
0
apply Theorem 3 to the transpose of the log log
n -by-n matrix obtained by stacking the log n Mi matrices.
This takes O(n) space and O(n log n) time. This serves as a subrow maximum data structure for each Mi0 ,
so we can apply Theorem 2 to each Mi0 separately, which takes a total of O( logn n logloglogn n log( logloglogn n )) = O(n)
additional space and O(n log log n) time.
We repeat the above preprocessing on the transpose of M . Now consider a submatrix maximum query. If
the range of rows starts inside some Mi and ends inside another Mi0 , the query can be decomposed into two
queries fully within Mi and Mi0 , respectively, and an infix corresponding to a range of rows of M 0 . The maximum in the infix can be computed in O(log log n) time using the structure constructed for M 0 . Consequently,
it is enough to show how to answer a query in O(log log n) time when the range of rows is fully within a single
Mi . In such case, if the range of rows starts inside some Mi,j and ends inside another Mi,j 0 , the query can be
decomposed into a prefix fully within Mi,j , an infix corresponding to a range of rows in Mi0 and a suffix fully
within some Mi,j 0 . The query on the infix can be answered using the data structure for Mi0 . Consequently,
we reduced the query in O(log log n) time to four queries such that the range of rows in each query is fully
within a single Mi,j . Since each Mi,j consists of O(log log n) rows of M , by taking the union of the rows of M
corresponding to all these Mi,j ’s and also including the row containing the maximum in the infixes, we have
identified, in O(log log n) time, a set of O(log log n) rows of M that contain the desired submatrix maximum.
Now we repeat the same procedure on the transpose of M to identify a set of O(log log n) columns of
M that contain the desired submatrix maximum. Since a submatrix of a Monge matrix is also Monge, the
submatrix of M corresponding to these sets of candidate rows and columns is an O(log log n) × O(log log n)
Monge matrix. By running the SMAWK algorithm [2] in O(log log n) time on this small Monge matrix, we
can finally determine the answer.
t
u

4

Lower Bound

A predecessor structure stores a set of n integers S ⊆ [0, U ), so that given x we can determine the largest
y ∈ S such that y ≤ x. As shown by Pǎtraşcu and Thorup [23], for U = n2 any predecessor structure
8

consisting of O(n polylog(n)) words needs Ω(log log n) time to answer queries, assuming that the word size
is Θ(log n). We will use their result to prove that our structure is in fact optimal.
Given a set of n integers S ⊆ [0, n2 ) we want to construct an n × n Monge matrix M such that the
predecessor of any x in S can be found using one submatrix maximum query on M and O(1) additional
time (to decide which query to ask and then return the final answer). Then, assuming that for any n × n
Monge matrix there exists a data structure of size O(n polylog(n)) answering submatrix maximum queries
in o(log log n) time, we can construct a predecessor structure of size O(n polylog(n)) answering queries in
o(log log n) time, which is not possible. The technical difficulty here is twofold. First, M should be Monge.
Second, we are working in the indexing model, i.e., the data structure for submatrix maximum queries
should be able to access the matrix. Therefore, for the lower bound to carry over, M should have the
following property: there is a data structure of size O(n polylog(n)) which retrieves any M [i, j] in O(1) time.
Guaranteeing that both properties hold simultaneously is not trivial.
Before we proceed, let us comment on the condition S ⊆ [0, n2 ). While quadratic universe is enough to
invoke the Ω(log log n) lower bound for structures of size O(n polylog(n)), our reduction actually implies
that even for larger polynomially bounded universes, i.e., S ⊆ [0, nc ), for any fixed c, it is possible to
construct an n × n Monge matrix M such that the predecessor of x in S can be found with O(1) submatrix
maximum queries on M and O(1) additional time (and, as previously, any M [i, j] can be retrieved in O(1)
time with a structure of size O(n)). This is a consequence of the following lemma.
Lemma 4. For any constant c ≥ 2, predecessor queries on a set of n integers S ⊆ [0, nc ) can be reduced in
O(1) time to O(1) predecessor queries on a set of n integers S 0 ⊆ [0, n2 ) with a structure of size O(n).
Proof. First we describe a weaker version of the reduction for c = 4, where the resulting set of integers is
S 0 ⊆ [0, 3n2 ).
Let S = {x1 , x2 , . . . , xn }. We represent every xi in base n2 as xi = yi · n2 + zi , where yi , zi ∈ [0, n2 ). We
create a new set Y ⊆ [0, n2 ) storing all yi s and a new set Z ⊆ [0, n2 ) storing all zi s. For any t ∈ [0, n2 ), let
rankY (t) and rankZ (t) denote the rank of t in Y and Z, respectively, where rank is the number of smaller
elements in the set. We create another set R ⊆ [0, n2 ) storing elements of the form rankY (yi ) · n + rankZ (zi ).
We also create a perfect hash table of size O(n) mapping yi to rankY (yi ) and zi to rankZ (zi ). To find the
predecessor of x in S, we first represent it as x = y · n2 + z. We claim that it is always possible to reduce
locating the predecessor of x in S to the case where y ∈ Y and z ∈ Z in two steps. Let y 0 denote the
predecessor of y in Y and z 0 denote the predecessor of z in Z.
1. If z 0 is not defined, we decrease y by one (adjusting y 0 if necessary) and replace z by the largest element
of Z. Otherwise, we replace z by z 0 .
2. If y 0 is not defined, x has no predecessor in S. Otherwise, if y 0 6= y we replace y by y 0 and z by the
largest element of Z.
Both steps maintain the predecessor of x in S and take O(1) time. Finally, having reduced the general
case so that y ∈ Y and z ∈ Z, we locate the predecessor of x0 = rankY (y) · n + rankZ (z) in R. Because y ∈ Y
and z ∈ Z, both rankY (y) and rankZ (z) can be retrieved in O(1) time from the perfect hash tables. The
predecessor of x0 in R corresponds to the predecessor of x in S, because comparing two elements of the same
set is equivalent to comparing their ranks there. Formally, xi ≤ x iff yi < y or yi = y and zi ≤ z, which is
equivalent to rankY (yi ) < rankY (y) or rankY (yi ) = rankY (y) and rankZ (zi ) ≤ rankZ (z), which because the
ranks are all from [0, n) can be stated as rankY (yi ) · n + rankZ (zi ) ≤ rankY (y) · n + rankZ (z). Consequently, a
predecessor query on S can be reduced into one predecessor query into each of Y, Z, R. These three sets can
be combined into a single set S 0 ⊆ [0, 3n2 ), such that predecessor queries in either of them can be answered
with predecessor queries on S 0 , by simply shifting every element of Z by n2 and every element of R by 2n2 .
Finally, the size of S 0 , which is up to 3n right now, can be reduced to n as follows. Let the elements of S 0
be x1 < x2 < . . . < x3n . We store every x3i , for i = 1, 2, . . . , n in the predecessor structure. Additionally,
for every i we explicitly store x3i+1 and x3i+2 . Knowing the predecessor xi of x among the chosen elements
allows us to find its predecessor among all elements in O(1) time by additionally inspecting x3i+1 and x3i+2 .
9

Now we explain how to extend the above reduction for any constant c ≥ 2, while also ensuring that the
resulting set of integers is S 0 ⊆ [0, n2 ). If n < 5, we answer predecessor queries naively in O(1) time. If n ≥ 5,
by modifying the above reduction so that every xi is represented as yi · n2 + zi , where yi ∈ [0, nc−2 ) and
zi ∈ [0, n2 ), we obtain a set of n integers from [0, nc−1 ). Hence, by iterating c − 3 times we finally obtain a set
of n integers from [0, n3 ). Then one final iteration, where we represent every xi as yi ·B+zi , with yi , zi ∈ [0, B)
with B = dn1.5 e, allows us to reduce the size of the universe to 2B + n2 , which is at most 2n2 for n ≥ 5. To
reduce the size of the universe to n2 , we divide every xi by 2. Let the resulting set be x01 < x02 < . . . x0n0 . We
store a perfect hash table mapping x0i to x0i−1 (if it exists) and a list of elements xj such that bxj /2c = x0i
(note that there are at most two such js). To find the predecessor of x, we then find the predecessor x0i of
bx/2c in the obtained set. Then, we inspect all the elements stored on the lists of x0i and x0i−1 (accessed from
t
u
the entry of x0i in the perfect hash table) and return the largest not exceeding x in O(1) time.
The following propositions are easy to verify:
Proposition 1. An m × n matrix M is Monge iff M [i, j] + M [i + 1, j + 1] ≥ M [i + 1, j] + M [i, j + 1] for
all i = 1, 2, . . . , m − 1 and j = 1, 2, . . . , n − 1.
Proposition 2. If a matrix M is Monge, then for any vector H the matrix M 0 , where M 0 [i, j] =
M [i, j] + H[j] for all i, j, is also Monge.
Proposition 3. If a matrix M is partial Monge, then it remains partial Monge after replacing any element
of M by a blank, so long as the defined entries in each row and in each column remain contiguous.
Proposition 4. If a m-by-n matrix M is (partial) Monge, then the (m + 1)-by-n matrix resulting by
replacing any row of M by two identical copies of that row is also (partial) Monge. An analogous statement
holds for duplicating any column of M .
Theorem 5. For any set of n integers S ⊆ [0, n2 ), there exists a data structure of size O(n) returning any
M [i, j] in O(1) time, where M is a Monge matrix such that the predecessor of x can be found using O(1)
time and one submatrix maximum query on M .
Proof. We partition the universe [0, n2 ) into n parts [0, n), [n, 2n), . . .. The i-th part [i · n, (i + 1) · n) defines
a Monge matrix Mi consisting of 2 + |S ∩ [i · n, (i + 1) · n)| rows and n columns. The first and the last row
are artificial, and others encode the elements of S ∩ [i · n, (i + 1) · n). The idea is to encode the predecessor
of x ∈ [0, n2 ) by the maximum element in the (x mod n + 1)-th column of Mbx/nc . We first describe how
these matrices are defined, and then show how to stack them together.
Consider any 0 ≤ i < n. Every element in S ∩ [i · n, (i + 1) · n) = {a1 , a2 , . . . , ak } has a unique
corresponding row in Mi . Let aj = i · n + a0j , so that a01 < a02 < . . . < a0k and a0j ∈ [0, n) for all j, and also
define a0k+1 = n. We describe an incremental construction of Mi . For technical reasons, we start with an
artificial top row containing n − 1, n − 2, . . . , 1. Then we add the rows corresponding to a01 , a02 , . . . , a0k . The
row corresponding to a0j consists of three parts. The middle part starts at the (a0j + 1)-th column, ends at the
a0j+1 -th column, and contains only n’s. The elements in the left part increase by 1 and end with n − 1 at the
a0j -th column, similarly the elements in the right part (if any) start with n − 1 at the (a0j+1 + 1)-th column
and decrease by 1. Formally, the k-th element of the (j + 1)-th row, denoted Mi [j + 1, k], is defined as follows.

0
0

n − 1 − aj + k if k ∈ [1, aj ]
0
Mi [j + 1, k] = n
(1)
if k ∈ [aj + 1, a0j+1 ]


0
0
n − k + aj+1
if k ∈ [aj+1 + 1, n]
Finally, we end with an artificial bottom row containing 1, 2, . . . , n. See Figure 2 for an example. We
need to argue that every Mi is Monge. By Proposition 1, it is enough to consider every pair of adjacent
rows r1 , r2 there. Define r10 [j] = r1 [j] − r1 [j − 1] and similarly r20 [j] = r2 [j] − r2 [j − 1]. To prove that Mi is
Monge, it is enough to argue that r20 [j] ≥ r10 [j] for all j ≥ 2. By construction, both r10 and r20 are of the form
1, 1, . . . , 1, 0, 0, . . . , 0, −1, −1, . . . , −1, and all 0’s in r20 are on the right of all 0’s in r10 . Therefore, Mi is Monge.
10

Now one can observe that the predecessor of x ∈ [0, n2 ) can be found by looking at the (x mod n + 1)-th
column of Mbx/nc . We check if x < a1 , and if so return the predecessor of a1 in the whole S. This can
be done in O(1) time and O(n) additional space by explicitly storing a1 and its predecessor for every i.
Otherwise we know that the predecessor of x is aj such that x mod n ∈ [a0j , a0j+1 ), and, by construction, we
only need to find j ∈ [1, k] such that the (x mod n + 1)-th element of row j + 1 in Mi is n. This is exactly
a subcolumn maximum query.
We cannot simply concatenate all Mi ’s to form a larger Monge matrix. We use Proposition 2 instead.
Initially, we set M = M0 . Then we consider every other Mi one-by-one maintaining invariant that the current
M is Monge and its last row is 1, 2, . . . , n. In every step we add the vector H = [n − 1, n − 3, . . . , −n + 1]
to the current matrix M , obtaining a matrix M 0 whose last row is n, n − 1, . . . , 1. By Proposition 2, M 0 is
Monge. Then we can construct the new M by appending Mi without its first row to M 0 . Because the first
row of Mi is also n − 1, n − 2, . . . , 1, the new M is also Monge. Furthermore, because we add the same value
to all elements in the same column of Mi , answering subcolumn maximum queries on Mi can be done with
subcolumn maximum queries on the final M . The right side of Figure 2 depicts the final Monge matrix M .
We need to argue that elements of M can be accessed in O(1) time using a data structure of size O(n).
To retrieve M [j, k], first we lookup in O(1) time the appropriate Mi from which it originates. This can be
preprocessed and stored for every j in O(n) total space and allows us to reduce the question to retrieving
Mi [j 0 , k]. Because Proposition 2 is applied exactly n − 1 − i times after appending Mi to the current M ,
then we can return Mi [j 0 , k] + (n − 1 − i) · H[k]. To find Mi [j 0 , k], we just directly use Equation 1, which
t
u
requires only storing a01 , a02 , . . . , a0n in O(n) total space.

57
 54

 50

 43

 41

 38

 37

 36

M =
 29
 22

 20

 16

 15

 8

 7

 4
1


M0

M1

M2

M3


87654321
= 5 6 7 8 8 8 8 8
12345678


87654321
=
12345678


87654321
6 7 8 8 8 7 6 5



=
3 4 5 6 7 8 7 6
2 3 4 5 6 7 8 8
12345678


87654321
=
12345678





M4 =

87654321
12345678






87654321
6 7 8 8 8 8 7 6

M5 = 
2 3 4 5 6 7 8 8
12345678


87654321
M6 =
12345678


87654321
7 8 8 8 7 6 5 4

M7 = 
4 5 6 7 8 8 8 8
12345678

42
41
37
32
32
29
28
27
22
17
17
13
12
7
8
5
2

27
28
24
21
23
20
19
18
15
12
14
10
9
6
8
6
3

12
15
11
10
13
11
10
9
8
7
10
7
6
5
8
7
4

−3
1
−2
−1
3
2
1
0
1
2
6
4
3
4
7
8
5

−18
−13
−15
−12
−8
−7
−8
−9
−6
−3
2
1
0
3
6
8
6

−33
−27
−28
−23
−19
−18
−17
−18
−13
−8
−3
−2
−3
2
5
8
7


−48
−41 

−41 

−34 

−30 

−29 

−27 

−27 

−20 

−13 

−8 

−6 

−6 

1 

4 

8 
8

Fig. 2. Reduction for n = 8 and S = {8 · 0 + 3, 8 · 2 + 2, 8 · 2 + 5, 8 · 2 + 6, 8 · 5 + 2, 8 · 5 + 6, 8 · 7 + 1, 8 · 7 + 4}.

5

Data structure for partial Monge matrices

Our goal in this section is to extend the solution described in Section 3 to partial Monge matrices. Recall
that in a partial Monge matrix M , for any i < j and k < `, the condition M [i, k] + M [j, `] ≥ M [i, `] + M [j, k]
holds only if all of M [i, k], M [j, `], M [i, `], M [j, k] are defined. Not all entries in M are defined, but the
defined entries in every row and every column are contiguous. Let si and ti denote the first and last columns
containing defined entries in the i’th row respectively. We assume that we know the coordinates of at least
one of the defined entries. This allows us to find all si ’s and ti ’s in O(n log n) time.
11

The following Lemma states that we can implicitly fill appropriate constants instead of the undefined
(blank) entries to turn a partial Monge matrix into a full Monge matrix:
Lemma 5. The blank entries in an m × n partial Monge matrix M can be implicitly replaced in O(m + n)
time so that M becomes Monge and each Mij can be returned in O(1) time.
Proof. Let si (resp. ti ) denote the index of the leftmost (resp. rightmost) column that is defined in row i.
Since the defined (non-blank) entries of each row and column are continuous we have that the sequence
s1 , s2 , . . . , sm starts with a non-increasing prefix s1 ≥ s2 ≥ . . . ≥ sa and ends with a non-decreasing
suffix sa ≤ sa+1 ≤ . . . ≤ sm . Similarly, the sequence t1 , t2 , . . . , tn starts with a non-decreasing prefix
t1 ≤ t2 ≤ . . . ≤ tb and ends with a non-increasing suffix tb ≥ tb+1 ≥ . . . ≥ tm .
We partition the blank region of M into four regions: (I) entries that are above and to the left of M [i, si ]
for i = 1, . . . , a, (II) entries that are below and to the left of M [i, si ] for i = a + 1, . . . , m, (III) entries that
are above and to the right of M [i, ti ] for i = 1, . . . , b, (IV) entries that are below and to the right of M [i, ti ]
for i = b + 1, . . . , n. We first describe how to replace all entries in region I to make them non-blank and
obtain a valid partial Monge matrix (whose blank entries are only in regions II, III, and IV). The remaining
regions are handled in a similar manner, one after the other.
We describe our method for filling in the blank entries in region I in two steps. In the first step we
show how to implicitly fill in the blanks in a lower right triangular Monge matrix so that each filled blank
entry can be computed in O(1) time. By a lower right triangular Monge matrix we mean a partial Monge
square matrix with n rows and columns, such that, for all 1 ≤ i ≤ n, si = n − i + 1. In the second step
we explain that any m-by-n partial Monge matrix whose blank entries are in region I can be turned into
a lower right triangular Monge matrix with at most m + n rows and columns. The only operations used
in the transformation are duplicating rows, duplicating columns, and turning elements into blanks. We will
show an O(m + n) procedure for computing two tables. One specifying, for each row index 1 ≤ i ≤ m, the
corresponding row index in the larger O(m + n) triangular matrix. The second is an analogous table for the
columns indices. The lemma then follows for the blank entries in region I. The other regions are treated by
reducing to the region I case, one after the other.
We now describe how to fill in the blank regions in a lower right triangular Monge matrix. Let W denote
the largest absolute value of any non-blank entry in M (We can find W by applying the algorithm of Klawe
and Kleitman [19]). Intuitively, we would like to make every M [i, j] in the upper left triangle very large.
However, we cannot simply assign the same large value to all of them, because then the Monge inequality
would not be guaranteed to hold if more than one of the four considered elements belongs to the replaced
part of the matrix. A closer look at all possible cases shows that setting all the entries of each diagonal to the
same value does work. More precisely, we replace the blank element M [i, j] with 3W [2(n − i − j) + 1]. Thus,
each element in the first diagonal off the main diagonal (i + j = n) is set to 3W , the elements of the second
diagonal off the main diagonal are set to 9W , etc. Note that the maximum element in the resulting matrix is
O(nW ). To prove that the resulting new matrix M 0 is Monge, it suffices, by Proposition 1, to show that, for all
1 ≤ i, k < n, M 0 [i, k]+M 0 [i+1, k+1]−M 0 [i, k+1]−M 0 [i+1, k] ≥ 0. To this end we consider the following cases:
1. i + k > n, so all M [i, k], M [i + 1, k + 1], M [i, k + 1], M [i + 1, k] are non-blank, and the inequality holds
because M is partial Monge.
2. i + k = n, so M [i, k] is blank and M [i + 1, k + 1], M [i, k + 1], M [i + 1, k] are non-blank. Then
M 0 [i, k] + M 0 [i + 1, k + 1] − M 0 [i, k + 1] − M 0 [i + 1, k] = 3W + M 0 [i + 1, k + 1] − M 0 [i, k + 1] − M 0 [i + 1, k] ≥
3W − 3W = 0.
3. i + k = n − 1, so M [i, k], M [i, k + 1], M [i + 1, k] are blank, and M [i + 1, k + 1] is non-blank. Then
M 0 [i, k] + M 0 [i + 1, k + 1] − M 0 [i, k + 1] − M 0 [i + 1, k] = 9W + M [i + 1, k + 1] − 3W − 3W ≥ 3W − W ≥ 0.
4. i + k < n − 1, so all M [i, k], M [i + 1, k + 1], M [i, k + 1], M [i + 1, k] are blank. Then,
M 0 [i, k] + M 0 [i + 1, k + 1] − M 0 [i, k + 1] − M 0 [i + 1, k] = 0.
Hence the new matrix M 0 is indeed Monge.
Next, we describe how to turn any m-by-n partial Monge matrix M whose blank entries are in region
I into a slightly larger lower right triangular matrix M 0 . This is done by duplicating some rows or columns
12

of M and replacing by blanks a nonempty prefix in all but a single copy. Thus, each row r (column c) of
M has at least one appearance in M 0 in which no elements are replaced by blanks. We say that r (c) is
mapped to such an appearance in M 0 . Propositions 3 and 4 guarantee that M 0 is partial Monge. For ease
of presentation we describe the process as if we actually transform the M into M 0 , although in reality we
only need to compute the mappings of rows and columns.
The assumption that the blank entries are in region I implies that s1 ≥ s2 ≥ · · · ≥ sm = 1 and that
t1 = t2 = · · · = tm = n. We first guarantee that the si ’s are strictly decreasing. We do this by iterating
through the si ’s. If si = si−1 , we duplicate the column si of M (i.e., shift all columns at indices greater
than i by one position, and insert a copy of column si at the vacant index si + 1), make M [i − 1, si ] blank,
and mark the column currently at index si as a duplicate (the index of this column might change later
if columns with smaller indices will be duplicated). This column duplication has the effect of increasing
by 1 all sj ’s for j < i. Let M 0 denote the matrix obtained from M at the end of this process, and let s0i
denote the index of the first defined entry in row i of M 0 . If M 0 does not have m + n columns, we insert a
sufficient number of copies of first column of M 0 to make it so. We construct a table c[·] which keeps track
of the mapping of columns of M to M 0 by recording for each non-duplicate row its original index in M
and its index in M 0 . Clearly, computing c[·] and the indices s0i ’s can be done in O(m) time without actually
duplicating the columns. See Figure 3 (middle) for an illustration.
We will further modify M 0 and use a table r[·] to keep track of the mapping from rows of M to rows of
0
M . For convenience, we define s00 = m + n + 1, and r[0] = 0. We iterate through the sequence s01 , s02 , . . . , s0m .
We add to M 0 s0i−1 − s0i copies of row i of M 0 , and, for j = 1, 2, . . . , s0i−1 − s0i − 1, replace the prefix of
length j from the j’th copy by blanks, so only the last copy remains unchanged. We therefore set r[i] to
r[i − 1] + s0i−1 − s0i . Clearly, we can compute the table r[·] in O(m + n) time without actually modifying
M 0 . See Figure 3 (right) for an illustration.

Fig. 3. A staircase matrix M is transformed into a triangular matrix M 0 in two steps by duplicating columns and
rows. Defined entries are gray, undefined white, and duplicated columns/rows black.

Finally, to obtain the value with which the blank entry at M [i, j] should be replaced when converting
M into a full Monge matrix, we return 3W [2(m + n − r[i] − c[j]) + 1].
Regions II, III, and IV can be handled symmetrically to region I. To handle undefined entries in region
II, we implicitly reverse the order of the rows and negate all the elements of the matrix. It is easy to verify
that the resulting matrix is Monge with undefined entries in region I. We then implicitly fill in the undefined
values using the method described above, negate all the elements and revert the order of rows to its original
order. The transformation for region III is reversing the order of columns and negating all elements, and
the transformation for region IV is reversing the order of both rows and columns. Note that to make M full
Monge we first need to fill the blanks in region I, then calculate the new value of W and fill the blanks in
region II accordingly, and so on.
t
u
13

For subcolumn (or subrow) maximum queries, the above lemma implies that we can handle partial
Monge matrices in the same bounds as full Monge matrices (i.e., the bounds of Theorem 3 and Corollary 1
also apply to partial Monge matrices). Upon subcolumn query (a column c and a range of rows R) we first
restrict R to the defined entries in the column c and only then query the data structure.
For submatrix queries however, this trick only works if the query range is entirely defined. In general, it
does not work because the defined entries in the query range do not necessarily form a submatrix. Handling
submatrix queries is therefore more complicated. Our solution is based on the following decomposition.
5.1

Decomposing a partial Monge matrix into staircase matrices

Our data structure relies on a decomposition of M into staircase matrices. A partial matrix is staircase if the
defined entries in its rows either all begin in the first column and the ti s are monotone, or all end in the last
column and the si s are monotone. It is well known (cf. [1]) that by cutting M along columns and rows, it can
be decomposed into staircase matrices {Mi } such that each row is covered by at most two matrices, and each
column is covered by at most three matrices. For completeness, we describe such a decomposition below.
Lemma 6. A partial matrix M can be decomposed into staircase matrices {Mi } such that each row is
covered by at most two matrices, and each column is covered by at most three matrices.
Proof. Let si and ti denote the smallest and largest column index in which an element in row i is defined,
respectively. The fact that the defined entries of M are contiguous in both rows and columns implies that the
sequence s1 , s2 , . . . , sm consists of a non-increasing prefix and a non-decreasing suffix. Similarly, the sequence
t1 , t2 , . . . , tm consists of a non-decreasing prefix and a non-increasing suffix. It follows that the rows of M can
be divided into three ranges - a prefix where s is non-increasing and t is non-decreasing, an infix where both
s and t have the same monotonicity property, and a suffix where s is non-decreasing and t is non-increasing.
The defined entries in the prefix of the rows can be divided into two staircase matrices by splitting M at
t1 , the largest column where the first row has a defined entry. Similarly, the defined entries in the suffix of
the rows can be divided into two staircase matrices by splitting it at tm , the largest column where the last
row has a defined entry. The defined entries in the infix of the rows form a double staircase matrix. It can
be broken into staircase matrices by dividing along alternating rows and columns as shown in Figure 4.
It is easy to verify that, in the resulting decomposition, each row is covered by at most two staircase
matrices, and each column is covered by at most three staircase matrices. Also note that every set of
consecutive columns whose defined elements are in exactly the same set of rows are covered in this
decomposition by the same three row-disjoint staircase matrices.
t
u
Before we use the above decomposition for our data structure, we show how it can be used to prove
that, if M is an m × n TM (or Monge) staircase matrix, then the number of breakpoints of M is O(m).
This result illustrates the use of the decomposition, it was used in the data structure of [17], and we believe
is of independent interest.
Theorem 6. Let M be a partial m × n matrix in which the defined entries in each row and in each column
are contiguous. If M is TM (i.e., for all i < j, k < ` where M [i, k], M [i, `], M [j, k], M [j, `] are all defined,
M [i, k] ≤ M [j, k] =⇒ M [i, `] ≤ M [j, `]), then the number of breakpoints of M is O(m).
Proof. We first show that the number of breakpoints of an m × n TM staircase matrix is at most 2m. We
focus on the case where the defined entries of all rows begin in the first column and end in non-decreasing
columns. In other words, for all i, si =1 and ti ≤ ti+1 . The other cases are symmetric.
A breakpoint is a situation where the maximum in column c is at row r1 and the maximum in column
c + 1 is at a different row r2 . We say that r1 is the departure row of the breakpoint, and r2 is the entry row
of the breakpoint. There are two types of breakpoints: decreasing (r1 < r2 ), and increasing (r1 > r2 ). We
show that (1) each row can be the entry row of at most one decreasing breakpoint, and (2) each row can be
the departure row of at most one increasing breakpoint.
14

Fig. 4. A decomposition of a partial matrix (where the defined entries are gray and the undefined white) into staircase
matrices (defined by solid thick black lines) and into blocks of consecutive columns with the same defined entries
(indicated by thin vertical red lines).

(1) Assume that row r2 is an entry row of two decreasing breakpoints: One is the pair of entries
(r1 , c1 ), (r2 , c1 + 1) and the other is the pair (r3 , c2 ), (r2 , c2 + 1). We know that r1 < r2 , r3 < r2 , and
wlog c2 > c1 + 1. Since the maximum in column c1 + 1 is in row r2 , we have M [r3 , c1 + 1] < M [r2 , c1 + 1].
However, since the maximum in column c2 is in row r3 , we have M [r3 , c2 ] > M [r2 , c2 ], contradicting the
total monotonicity of M . Note that M [r2 , c2 ] is defined since M [r2 , c2 + 1] is defined.
(2) Assume that row r1 is a departure row of two increasing breakpoints: One is the pair of entries
(r1 , c1 ), (r2 , c1 + 1) and the other is the pair (r1 , c2 ), (r3 , c2 + 1). We know that r1 > r2 and r1 > r3 . Since
the maximum in column c1 is in row r1 , we have M [r2 , c1 ] < M [r1 , c1 ]. However, since the maximum in
column c1 + 1 is in row r2 , we have M [r2 , c1 + 1] > M [r1 , c1 + 1], contradicting the total monotonicity
of M . Note that M [r1 , c1 + 1] is defined since M [r1 , c2 ] is defined.
The above two claims prove that the number of breakpoints of a staircase matrix is at most 2m. We use
this fact, and the above decomposition to staircase matrices to prove an O(m) bound for arbitrary partial
matrices.
Let bp(Mi ) denote the number of breakpoints
P in matrix Mi . Let mi denote the number of rows in Mi .
Since each row
appears
in
at
most
two
M
s,
i
i mi = O(m). The total number of breakpoints in all Mi s is
P
P
O(m) since i bp(Mi ) = i O(mi ) = O(m).
Consider now a partition of M into rectangular blocks Bj defined by maximal sets of contiguous columns
whose defined entries are at the same set ofP
rows, see Figure 4. There are O(m) such blocks. Notice that
the number of breakpoints of M is bp(M ) = j bp(Bj ) + O(m) (the O(m) term accounts for
Pthe possibility
of a new breakpoint between every two consecutive blocks). Therefore, it suffices to bound j bp(Bj ).
Consider some block Bj . As we mentioned above, the columns of Bj appear in at most three row-disjoint
staircase matrices M1 , M2 , M3 , in the decomposition of M . The column maxima of Bj are a subset of the
column maxima of M1 , M2 , M3 . Assume wlog that the indices of rows covered by Mi are smaller than those
covered by Mi+1 for every i = 1, 2.
The breakpoints of Bj are either breakpoints of M1 , M2 , M3 , or breakpoints that occur when the maxima
in consecutive columns of Bj originate in different Mi . However, since Bj is a (non-partial) TM matrix, its
15

column maxima are monotone. So once a column maximum originates in Mi , no maximum in greater columns
will ever originate in Mj for j < i. It follows that the numberPof breakpoints
P in Bj that are not breakpoints
of M1 , M2 , M3 is at most two. Since there are O(m) blocks, j bp(Bj ) ≤ i bp(Mi ) + O(m) = O(m). This
completes the proof of Theorem 6.
t
u
5.2

The data structure

We begin with a weaker result (Theorem 7), which is that one can answer submatrix maximum queries on
an n × n staircase matrix in O(log log n) time with a structure of size O(n log n). We will then (Theorem 8)
show how to reduce the space to O(n), and finally (Theorem 9) how to handle arbitrary partial Monge
matrices using the decomposition into staircase matrices.
We will need the following preliminary lemma, that follows quite easily from the persistent predecessor
structure of Chan [8].
Lemma 7. A collection S of O(n) weighted points on an n × n grid can be preprocessed in O(n log log n)
time and O(n) space, so that, given any (x, y), the maximum weight of a point (x0 , y 0 ) ∈ S such that x0 ≥ x
and y 0 ≥ y can be calculated in O(log log n) time.
Proof. We use the standard geometric idea of sweeping the grid with a horizontal line while maintaining a
data structure describing the current situation. The data structure is made partially persistent so that after
sweeping, given a query (x, y), we can retrieve the version of the structure corresponding to a horizontal line
passing through (x, y). Querying that version of the data structure will allow us to answer the request. The
data structure will be a predecessor structure made persistent using the result of Chan [8]. See Theorem 5
of [21] for a more detailed description of a similar lemma.
Denote the points by (xi , yi ) and their corresponding weights by wi . We assume that the weights are
distinct. We sweep the grid with a horizontal line starting at y = n. The predecessor structure stores xcoordinates of some of the already seen points. Coordinate xi is stored in the predecessor structure iff yi ≥ y
and there is no i0 such that yi0 ≥ y, xi0 ≥ xi and wi0 > wi . This is because otherwise the i0 -th point is a better
answer than the i-th point for any query processed using this or any future version of the data structure.
Consequently, the points whose x-coordinates are stored in the predecessor structure can be arranged so that
their x-coordinates are increasing and the weights decreasing. Then it follows that locating the maximum
weight of a point (x0 , y 0 ) ∈ S such that x0 ≥ x and y 0 ≥ y can be done by finding the successor of x in the
version of the predecessor structure corresponding to y. Maintaining the structure while sweeping the grid
is also done with a predecessor search. After having seen a new point (xi , yi ) we locate the predecessor of
xi . If the weight of the corresponding point is smaller than wi , we remove it from the structure and repeat.
A persistent predecessor search structure can be implemented in space O(n) while keeping the query
time O(log log n) [8]. Consequently, we can build in O(n log log n) time a structure of size O(n) answering
queries in O(log log n) time.
t
u
Theorem 7. Given an n × n staircase Monge matrix M , a data structure of size O(n log n) can be
constructed in O(n log n) time to answer submatrix maximum queries in O(log log n) time.
Proof. Because of left-right symmetry, we can assume that the defined entries in row i start in the first
column and end in column ti . Notice that either t1 ≤ t2 ≤ . . . ≤ tn or t1 ≥ t2 ≥ . . . ≥ tn . Without loss
of generality we will assume the latter. This is enough because we will not be explicitly using the Monge
f) where the undefined
property in our solution, except for applying Theorem 4 on a copy of M (called M
entries are appropriately filled.
We partition M into full Monge matrices using a standard method: First, create a full Monge matrix by
taking the upper-left fragment [1, n/2] × [1, tn/2 ] of M . Then, recursively decompose the staircase matrices
created by taking the upper-right fragment [1, n/2]×[tn/2 +1, n] and the lower-left fragment [n/2+1, n]×[1, n]
of M . See Figure 5. It is easy to verify that the decomposition consists of at most 2n full Monge matrices
(called fragments). The decomposition has other useful properties on which we elaborate further.
16

j0
i0

j’

j1
B

i’
A

C

i1

(a)

(b)

(c)

Fig. 5. (a) A staircase n × n Monge matrix partitioned into 2n smaller full Monge matrices (fragments). (b) A query
range [i0 , i1 ] × [j0 , j1 ] decomposed into two full Monge matrices A and B and one dominance query C. (c) The
dominance query as vertical and horizontal lines (the green fragment is fully inside the range and the blue and red
fragment intersect the horizontal line).

Consider a query range [i0 , i1 ] × [j0 , j1 ]. To find the maximum (defined) M [i, j] over all i ∈ [i0 , i1 ] and
j ∈ [j0 , j1 ] we proceed as follows. The simple case is when the query range is fully within the defined part of
f) where the undefined entries are
M . To handle this case, we apply Theorem 4 on a copy of M (denoted M
appropriately (and implicitly) filled using Lemma 5. This allows us to do submatrix queries in O(log log n)
time when the query range is fully defined. Otherwise, we decompose the query into three parts. The first
part, which we call a dominance maximum query, is to find the maximum M [i, j] over all i ≥ i0 and j ≥ j 0 ,
for i0 , j 0 to be defined shortly. The other two are submatrix maximum queries fully within the defined
f in O(log log n) time). The
part of M (and hence can be processed by querying the structure built for M
decomposition is performed in O(1) time by setting j 0 = ti1 +1 + 1 and choosing the smallest i0 ≥ i0 such
that ti0 < j1 (which can be preprocessed for every possible j1 in O(n) space). The two submatrix maximum
queries are therefore over the full Monge matrices [i0 , i1 ] × [j0 , j 0 − 1] and [i0 , i0 − 1] × [j 0 , j1 ]. Hence, it is
enough to focus on answering dominance maximum queries.
To answer a dominance maximum query (i.e., to find the maximum M [i, j] over all i ≥ i0 and j ≥ j 0 ) we
use the partition of M into full Monge matrices (fragments). Every such fragment is either fully inside the
query range, fully outside of the query range, or intersected by the query range boundary.
Fragments inside the query range. A fragment [r0 , r1 ] × [c0 , c1 ] is fully inside the query range iff r0 ≥ i0
and c0 ≥ j 0 . This observation allows us to reduce computing the maximum over all matrices fully inside the
query to the problem defined in Lemma 7. The reduction is simply that for every fragment [r0 , r1 ] × [c0 , c1 ]
we create a point (r0 , c0 ) and set its weight to be the maximum inside the fragment. As a result, we create
f to create every point separately takes total
at most O(n) points on the n × n grid. Using Theorem 2 on M
O(n log log n) in the preprocessing time, so in O(n log log n) time we can construct a structure of size O(n)
answering queries in O(log log n) time.
Fragments intersected by the query range. We are left only with finding the maximum over all
fragments intersected by the boundary of our dominance maximum query. We partition these fragments
into three groups. The first consists of the single fragment containing M [i0 , j 0 ]. The maximum there can be
f in O(log log n) time. All other fragments intersected by the
found with a submatrix maximum query on M
boundary are either intersected by the horizontal line y = i0 or the vertical line x = j 0 , but not both. We
show how to find the maximum over all matrices intersected by the horizontal line y = i0 and fully to the
right of the vertical line x = j 0 (the other case is symmetric).
17

By the properties of our decomposition scheme, there are at most log n fragments intersected by any
horizontal line, and they can be arranged in the natural left-to-right order. For every possible horizontal
line, we store these at most log n fragments in an array. For every fragment we store the coordinates of its
corresponding submatrix of M and the maximum in all of its entries below the horizontal line. The array is
additionally equipped with the maximum over all maxima in each one of its suffixes. Such preprocessed data
allows us to find the maximum over all fragments intersected by a horizontal line y = i0 and fully on the right
of a vertical line x = j 0 in O(log log n) time: First, we binary search over the array stored for y = i0 to locate
the leftmost fragment completely on the right of x = j 0 . Then we return the stored corresponding maximum.
Notice that the binary search also allow us to locate the fragment containing M [i0 , j 0 ]. Consequently, the
whole query time is O(log log n) using O(n log n) space for this part of the implementation. To guarantee
O(n log n) preprocessing time, we run the SMAWK algorithm on every fragment in the decomposition in
total O(n log n) time. This gives us the maximum in every row of every fragment. This is then enough to
construct all arrays in O(n log n) time.
t
u
We now proceed to improving Theorem 7 so that the structure needs just linear space. The main idea is to
partition the n×n staircase matrix M into cells of size log n×log n and then define a new smaller (n/ log n)×
(n/ log n) staircase matrix M 0 (whose entries correspond to cell-maxima in M ) on which we apply Theorem 7.
To implement this idea we need a number of additional auxiliary data structures, which take O(n) space in
total. We start with an auxiliary lemma, which will be used to provide constant-time access to entries of M 0 .
Lemma 8. Given an n × n Monge matrix M partitioned into log n × log n cells, a data structure of size
O(n) can be constructed in O(n log n) time to find the maximum in a given cell in O(1) time.
Proof. We partition M into n/ log n horizontal slices, each consisting of log n rows (and all columns). Consider
a single slice, which is a log n×n Monge matrix. We store its breakpoints c1 < c2 < . . . < ck (where k ≤ log n)
in an atomic heap, consequently allowing predecessor queries in O(1) time (this is exactly how the structure
from Corollary 1 works). Additionally, similarly to Lemma 2, for every i ≥ 2 we precompute the value of
mi =

max

j∈[ci−1 ,ci )

M [r(ci−1 ), j]

and augment these values with a (one dimensional) range maximum data structure. Here, r(c) denotes the
row containing the maximum element in the c-th column of the slice in question. Using two predecessor
queries and one range maximum query, the problem of finding the maximum in a given cell (which is fully
contained in a single horizontal slice) reduces in O(1) time to finding the maximum in at most two rows.
The total space is O(n/ log n · log n) = O(n) and the bottleneck in the preprocessing is computing the
breakpoints for all slices. The breakpoints of a single slice can be computed in O(log2 n) by adding one row
at a time, as done in the proof of Lemma 1. In total, this takes O(n/ log n · log2 n) = O(n log n) total time.
We repeat the above reasoning on the transpose of M . As a result, we either already know the maximum
element, or we have isolated at most two rows and at most two columns, such that the maximum lies in
one of these rows and one of these columns. This gives us at most four candidates for the maximum, which
can be retrieved and compared naively.
t
u
We are now ready to present our linear-space improvement to Theorem 7.
Theorem 8. Given an n × n staircase Monge matrix M , a data structure of size O(n) can be constructed
in O(n log n) time to answer submatrix maximum queries in O(log log n) time.
Proof. As in the proof of Theorem 7, we can assume that the defined entries in row i start in the first
column and end in column ti , and that t1 ≥ t2 ≥ . . . ≥ tn .
We partition M into cells of size log n × log n and then define a smaller (n/ log n) × (n/ log n) staircase
matrix M 0 . Notice that, unlike Lemma 8, M is a staircase Monge matrix (and not a full Monge matrix).
This means that there are three types of cells in M : fully defined, partially defined, and fully undefined.
An entry of M 0 is defined iff its corresponding cell in M is fully defined. In this case the entry is equal to
18

the maximum in the corresponding cell. The undefined entries of M 0 are the ones corresponding to either
partially defined or fully undefined cells of M . We appropriately (and implicitly) fill these entries using
f0 , on which we apply Lemma 8. This gives us constant-time
Lemma 5 to turn M ’ into a full Monge matrix M
0
access to the entries of M , so finally we can apply Theorem 7 to preprocess it in O(n) space and O(n log n)
time to answer submatrix maximum queries in O(log log n) time.
Regarding partially defined cells, we observe that there are at most 2n/ log n of them. Furthermore, they
can be arranged in a linear order, so that if the part of M corresponding to the i-th partially defined cell
0
0
+ 1 and [ci , c0i ] =
] and c0i + 1 = ci+1 or ri = ri+1
is [ri , ri0 ] × [ci , c0i ], then for all i either [ri , ri0 ] = [ri+1 , ri+1
0
[ci+1 , ci+1 ] (to be more precise, we might need to declare some fully defined cells partially defined to guarantee
this property). We create a predecessor structure storing all ri s and a separate predecessor structure storing all
ci s. We also compute the maximum in every partially defined cell and store them in an array (arranged in the
aforementioned linear order) augmented with a (one dimensional) range maximum structure. Computing the
maximum in all partially defined cells is done in O(n/ log n · log n · α(log n)) = O(n · α(log n)) time using [19].
By the same reasoning given in the proof of Theorem 7, it is enough to implement dominance maximum
queries on M . A dominance maximum query can be decomposed into (i) a dominance maximum query on
f0 , which can be answered in O(log log n) time, (ii) finding the maximum inside all partially defined cells
M
fully within the query range, and (iii) finding the maximum inside partially defined cells intersected by the
boundaries of the query range. All partially defined cells fully within the query range create a contiguous
interval in the linear order. The range can be determined in O(log log n) using the predecessor structures
storing all ri s and ci s, and then the maximum can be found in O(1) time with a (one dimensional) range
maximum query. It remains to calculate the maximum inside partially defined cells intersected by the
boundaries of the query range. We will describe how to process all partially defined cells intersected by the
horizontal boundary. Handling the vertical boundary is symmetric.
Let the dominance maximum query be specified by (i0 , j 0 ). We want to compute the maximum inside
the query range and belonging to a partially defined cell intersected by the horizontal line y = i0 . All such
cells create a contiguous interval in the linear order, which can be determined with two predecessor queries
in O(log log n) time. In the same complexity, we can find the leftmost such cell u which is not fully on the
left of the vertical line x = j 0 . We decompose the original query into a dominance maximum query inside u,
and the remaining part. The remaining part starts at a left boundary of a partially defined cell and consists
of the entries at or below y = i0 in all partially defined cells to the right of u. Consequently, the answer can
be preprocessed for every point on a left boundary of a partially defined cell using O(n/ log n · log n) = O(n)
space and O(n/ log n · log n · α(log n)) = O(n · α(log n)) time using [19]. The bottleneck in the preprocessing
is computing the maximum in every row of every partially defined cell.
It remains to describe how to handle the dominance query in u. In other words, after constructing in O(n log n) time an O(n) size structure, we have, in O(log log n) time, reduced an arbitrary
dominance maximum query into a dominance maximum query inside a single partially defined cell.
This cell is a smaller log n × log n staircase matrix, and furthermore there are at most 2n/ log n such
cells. By recursing on each of these smaller staircase matrices separately, we construct in additional
O(n/ log n · log n log log n) = O(n log log n) time an O(n/ log n · log n) = O(n) size structure, which reduces
the original dominance query, in additional O(log log log n) time, into a dominance maximum query inside
one of O(n/ log n · log n/ log log n) = O(n/ log log n) tiny log log n × log log n staircase matrix (each of them
being a submatrix of the original M ). By recursing again on every tiny staircase matrix separately, we
construct in additional O(n log log log n) time an O(n) size structure, which reduces the original arbitrary
dominance query in additional O(log log log log n) time into a dominance maximum query inside an
(log log log n) × (log log log n) submatrix of M . Such dominance maximum query can be answered naively
resulting in O(log log n + (log log log n)2 ) = O(log log n) total query time.
t
u
We are now ready to prove the main theorem of this section, which is that using Theorem 8 we
can actually implement submatrix maximum queries on arbitrary (and not just staircase) partial Monge
matrices. The idea is to partition the partial Monge matrix into staircase matrices, so that each row
and each column belong to O(1) staircase matrices. Such partitioning was used in [1,17] . We build the
19

data structure of Theorem 8 on each staircase matrix in the decomposition, and build an additional data
structure for queries spanning more than one staircase matrix.
Theorem 9. Given an n × n partial Monge matrix M , a data structure of size O(n) can be constructed in
O(n log n) time to answer submatrix maximum queries in O(log log n) time.
Proof. We partition M into staircase matrices as done in the proof of Lemma 6 (depicted in Figure 4). Recall
that the partition divides the rows of M into three ranges. The first range contributes two staircase matrices,
the second range creates a double staircase matrix, which is further broken into multiple staircase matrices,
and the third range contributes two staircase matrices. It is easy to verify that, in the resulting decomposition,
each row is covered by at most two staircase matrices, and each column is covered by at most three staircase
matrices. Additionally, the staircase matrices contributed by the second range can be partitioned into two
collections, such that any two matrices in the same collection are row-disjoint and column-disjoint.
The data structure consists of the following components. We apply Theorem 8 on every staircase
matrix in our partition. We also store additional data for both collections. By left-right symmetry, we can
assume that the ranges of rows and columns of the matrices in the collection are [r1 , r2 ), [r2 , r3 ), . . . and
[c1 , c2 ), [c2 , c3 ), . . ., respectively. We create a predecessor structure storing all ri ’s and a separate predecessor
structure storing all ci ’s. We also compute and store the maximum inside every staircase matrix in the
collection (this is done in total O(n · α(n)) time using the algorithm of Klawe and Kleitman [19]), and
augment these maxima with a (one dimensional) range maximum structure.
Now consider a submatrix maximum query [i0 , i1 ] × [j0 , j1 ]. We first query the O(1) structures built
for the staircase matrices corresponding to the first and the third range. Next, we consider each of the two
collections separately. To find the maximum M [i, j] over all i ∈ [i0 , i1 ] and j ∈ [j0 , j1 ], we use the predecessor
structures to determine in O(log log n) the following values (without loss of generality, they all exist):
1.
2.
3.
4.

i00
i01
j00
j10

such that i0 ∈ [ri00 , ri00 +1 ),
such that i1 ∈ [ri01 , ri01 +1 ),
such that j0 ∈ [cj00 , cj00 +1 ),
such that j1 ∈ [cj10 , cj10 +1 ).

We then query the structures built for the (i00 )-th, (i01 )-th, (j00 )-th, and (j10 )-th staircase matrix in the
collection. Now either we have already found the maximum, or it belongs to one of the staircase matrices
fully contained in the query range. Consequently, the maximum can be found in O(1) time with a single
(one dimensional) range maximum query.
t
u

References
1. A. Aggarwal and M. Klawe. Applications of generalized matrix searching to geometric algorithms. Discrete
Appl. Math., 27:3–23, 1990.
2. A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of a matrix-searching
algorithm. Algorithmica, 2(1):195–208, 1987.
3. S. Alstrup, G. S. Brodal, and T. Rauhe. New data structures for orthogonal range searching. In 41st FOCS,
pages 198–207, 2000.
4. A. Amir, J. Fischer, and M. Lewenstein. Two-dimensional range minimum queries. In 18th CPM, pages 286–294,
2007.
5. G. S. Brodal, P. Davoodi, M. Lewenstein, R. Raman, and S. S. Rao. Two dimensional range minimum queries
and Fibonacci lattices. In 20th ESA, pages 217–228, 2012.
6. G. S. Brodal, P. Davoodi, and S. S. Rao. On space efficient two dimensional range minimum data structures. In
18th ESA, pages 171–182, 2010.
7. R. E. Burkard, B. Klinz, and R. Rudolf. Perspectives of Monge properties in optimization. Discrete Appl. Math.,
70:95–161, 1996.
8. T. M. Chan. Persistent predecessor search and orthogonal point location on the word RAM. ACM Trans.
Algorithms, 9(3):22:1–22:22, 2013.

20

9. T. M. Chan, K. G. Larsen, and M. Pǎtraşcu. Orthogonal range searching on the RAM, revisited. In 27th SOCG,
pages 354–363, 2011.
10. B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal
on Computing, 17:427–462, 1988.
11. B. Chazelle and B. Rosenberg. Computing partial sums in multidimensional arrays. In 5th SOCG, pages
131–139, 1989.
12. E. D. Demaine, G. M. Landau, and O. Weimann. On Cartesian trees and range minimum queries. Algorithmica,
68(3):610–625, 2014.
13. A. Farzan, J. I. Munro, and R. Raman. Succinct indices for range queries with applications to orthogonal range
maxima. In 39th ICALP, pages 327–338, 2012.
14. M.L. Fredman and D.E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths.
J. Comput. Syst. Sci., 48(3):533–551, 1994.
15. H. Gabow, J. L. Bentley, and R.E Tarjan. Scaling and related techniques for geometry problems. In 16th STOC,
pages 135–143, 1984.
16. P. Gawrychowski, M. Lewenstein, and P. K. Nicholson. Weighted ancestors in suffix trees. In 22th ESA, pages
455–466, 2014.
17. P. Gawrychowski, S. Mozes, and O. Weimann. Improved submatrix maximum queries in Monge matrices. In
41st ICALP, pages 525–537, 2014.
18. H. Kaplan, S. Mozes, Y. Nussbaum, and M. Sharir. Submatrix maximum queries in Monge matrices and Monge
partial matrices, and their applications. In 23rd SODA, pages 338–355, 2012.
19. M. M. Klawe and D J. Kleitman. An almost linear time algorithm for generalized matrix searching. SIAM
Journal Discret. Math., 3(1):81–97, 1990.
20. T. Kopelowitz and M. Lewenstein. Dynamic weighted ancestors. In 18th SODA, pages 565–574, 2007.
21. M. Lewenstein. Orthogonal range searching for text indexing. In Space-Efficient Data Structures, Streams,
and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, volume 8066, pages
267–302. Springer, 2013.
22. Y. Nekrich. Orthogonal range searching in linear and almost-linear space. Comput. Geom., 42(4):342–351, 2009.
23. M. Pǎtraşcu and M. Thorup. Time-space trade-offs for predecessor search. In 38th STOC, pages 232–240, 2006.
24. H. Yuan and M. J. Atallah. Data structures for range minimum queries in multidimensional arrays. In 21st
SODA, pages 150–160, 2010.

21

