1 Introduction↩︎

Range minimum/maximum data structures are important substructures in the design of succinct and compressed data structures. The range maximum query (RMQ) problem asks us to preprocess an array so that, given a query range, we can return the position of a maximum element in that range (traditionally, RMQ refers to range minimum queries; we phrase the problem in terms of maxima, which is more convenient for our presentation, and the two variants are equivalent by negating all elements). In the one-dimensional setting, the input is an array of length \(n\) and a query is an interval \([i \mathinner{.\,.}j]\). In two dimensions, the input is an \(m\times n\) array and a query is an axis-parallel rectangle \([i_1 \mathinner{.\,.}i_2]\times[j_1 \mathinner{.\,.}j_2]\).

The RMQ problem has been studied in the literature in two distinct models: indexing and encoding models [1]. In the indexing model, the input array remains available at query time, and the data structure stores only auxiliary information, referred to as the index, to support the queries efficiently. In the encoding model, which is more relevant to this paper, queries are answered without access to the original input, and hence only the information relevant to answer queries is encoded within the data structure. The motivation behind the encoding model is twofold. First, it allows us to better understand the mathematical properties of the particular queries, and bound their effective entropy. Second, in some applications we need to support queries on an implicitly defined input that is well-defined but not stored at all (and not easy to compute in the query time). There has been a significant amount of research in the recent past on designing indexes and encodings for various range queries on arrays, such as 1D RMQ [2]–[13], 2D RMQ [4], [14]–[22], range min&max [23]–[26], range median and range mode [27]–[33], range selection and range top-\(k\) [23], [31], [34]–[36], and range majority and range minority [37]–[44]. See [20] for a survey on encodings for range queries on arrays.

RMQ is a basic primitive in data structures and algorithms. In one dimension, it is tightly connected to the lowest common ancestor (LCA) problem on trees, and has applications in suffix-array based text indexing, compressed suffix trees, document retrieval, geometric indexing and many others. In two dimensions, it is a special case of the orthogonal range-searching problem and is relevant as a subroutine in geometric indexing applications. The 1D problem is by now very well understood, with almost tight bounds known both in the indexing and the encoding models. On the other hand, the 2D problem is qualitatively more subtle: while almost optimal space indexes supporting constant-time queries are known, the encoding complexity is not well-settled. The gap between optimal encoding space and efficient query support for the 2D RMQ encoding problem remains one of the main structural differences between 1D and 2D RMQ, which is the problem we address in this paper.

1.1 Previous results↩︎

1.1.0.1 1D case.

The 1D RMQ problem has been widely studied, and many linear-space (i.e., \(\mathcal{O}(n \log n)\) bits) data structures with constant query-time have been proposed in the literature [45]–[47], most of them using the fact that RMQ is reducible to the LCA on the Cartesian tree of the input array. The index space is further reduced to \(\mathcal{O}(n/c)\) bits while supporting queries in \(\mathcal{O}(c)\) time [3], which is shown to be asymptotically optimal [4]. For the encoding model, the first breakthrough was due to Sadakane [48] who gave an encoding of size \(4n+o(n)\) bits that supports queries in constant time. The space usage is reduced to the optimal \(2n+o(n)\) bits by Fischer and Heun [3]. More recent work on 1D RMQ focused on the tradeoff between the query time and the lower order terms in the space usage: Liu [12] showed that any data structure supporting RMQ queries using \(2n - 1.5 \log n + r\) bits and query time \(t\), must satisfy \(r = n/(\log n)^{\mathcal{O}(t \log^2 t)}\), which closely matches the encoding of Liu and Yu [11] that uses \(2n - 1.5 \log n +n/(\frac{\log n}{t})^{t}\) bits to support queries in \(\mathcal{O}(t)\) time, for any parameter \(t> 1\). Thus the encoding complexity of 1D RMQ has been well-settled.

1.1.0.2 2D case.

For an \(m \times n\) input array, the multidimensional solution of Gabow et al. [49] gives a data structure that takes \(\mathcal{O}(N \log^2 N)\) bits and supports queries in \(\mathcal{O}(\log N)\) time, where \(N = mn\). The subsequent results [14], [16], [50] improved these bounds to \(\mathcal{O}(N \log N)\) bits and \(\mathcal{O}(1)\) query time. Brodal et al. [4] designed the first linear-bit (i.e., \(\mathcal{O}(N)\) bits) index that supports queries in constant time. They also proposed indexes that tradeoff query time for index size, which was further improved by [17].

For the encoding model, Demaine et al. [15] proved that there is no natural Cartesian-tree analogue for the 2D RMQ problem, and in particular showed a counting lower bound of \(\Omega(n^2\log n)\) bits for \(n\times n\) arrays. Brodal et al. [4] extended the lower bound to \(\Omega(mn\log m)\) bits for \(m\times n\) arrays with \(m\le n\). They also gave an \(\mathcal{O}(1)\)-query-time encoding using \(\mathcal{O}(mn\cdot \min\{m,\log n\})\) bits, which is optimal when \(\log n=\Theta(\log m)\) but not in general. The general encoding complexity was settled shortly afterwards by Brodal et al. [18], who obtained an encoding that takes \(\Theta(mn\log m)\) bits, matching the lower bound. However, their encoding does not support queries efficiently, and answering one may require decoding essentially the whole representation. Thus, prior to our work, there is a large gap between two extremes for the 2D RMQ encodings:

• an encoding with \(\mathcal{O}(1)\) query time using \(\mathcal{O}(mn\min\{m,\log n\})\) bits, and

• an asymptotically optimal \(\mathcal{O}(mn \log m)\)-bit encoding without efficient query support.

Bridging this gap is the main motivation for our work. The natural question is whether one can approach the optimal \(\Theta(mn\log m)\) space bound while still supporting fast queries. Our main result answers this positively by showing a trade-off between space and query time.

Two regimes of 1 are worth singling out. For every constant \(\epsilon > 0\), taking \(\kappa\) to be a sufficiently large constant yields an encoding of \(\mathcal{O}(mn(\log m + \log\log n))\) bits with queries in \(\mathcal{O}(\log^{\epsilon} n)\) time; the space is asymptotically optimal whenever \(n\) is at most exponential in \(m\). At the other extreme, taking \(\kappa = \log\log n\) drives the query time down to \(\mathcal{O}(1)\) at the cost of a multiplicative \(\log\log n\) blowup in space.

1.1.0.3 Overview.

3 reduces every query to a comparison between two distinguished points of the query rectangle, and 4 formalises the structure behind this comparison: every point is assigned an origin in an auxiliary tree built over the columns, and the two points produced by the reduction always share enough structure in this tree for the comparison to be resolved efficiently. 5 carries out the encoding itself in two passes. The baseline version (5.2) stores a small comparison structure at each node of the column tree and answers a query by repeatedly replacing one of the two current points with a substitute whose origin lies closer to the root; this matches 1 at \(\kappa = 1\). The full version (5.3) introduces a second tree, built over the depths of the column tree, that guarantees enough progress in each replacement to bound their number by its arity; tuning the arity yields the entire trade-off of 1. Finally, 6 constructs the two local primitives used by both encodings, by decomposing the active points of each node into \(\mathcal{O}(m)\) quarter-rows, inside which the weights are monotone with respect to the column.

2 Preliminaries↩︎

For integers \(i, j\) we write \([i \mathinner{.\,.}j]\) to denote \(\left\lbrace i, i + 1, \dots, j \right\rbrace\). Throughout the paper, the input is an \(m\times n\) array with rows indexed from \(1\) to \(m\), and columns indexed from \(1\) to \(n\). A point is a pair \((i,j)\in[1\mathinner{.\,.}m]\times[1\mathinner{.\,.}n]\). We treat the input as a function \(w\) mapping each point to a distinct weight; for a point \(p=(i,j)\), we write \(w(p)\) for its weight, \(\mathop{\mathrm{row}}(p)\mathrel{\vcenter{:}}= i\), and \(\mathop{\mathrm{col}}(p)\mathrel{\vcenter{:}}= j\). For a set of points \(S\), we write \(\max_w(S)\) for the unique point \(p \in S\) maximising \(w(p)\). A query rectangle is a set of the form \(R = [i_1 \mathinner{.\,.}i_2] \times [j_1 \mathinner{.\,.}j_2] \subseteq [1\mathinner{.\,.}m]\times[1\mathinner{.\,.}n]\), and the 2D RMQ problem asks, given such a rectangle \(R\), to return the heaviest point in it, namely \(\max_w(R)\).

We measure the space in bits and assume the standard word RAM model of computation, with word size \(\Theta(\log n)\), when describing the query algorithms.

We make use of the following 1D RMQ encoding.

In our encodings, we use representations of sets supporting the following operations. Given a set \(S \subseteq [1 \mathinner{.\,.}U]\),

• \(\mathop{\mathrm{rank}}_S(x)\) returns the number of elements of \(S\) that are not greater than \(x\), and

• \(\mathop{\mathrm{select}}_S(i)\) returns the \(i\)-th smallest element in \(S\).

We will only query rank on elements \(x \in S\) (i.e., only partial-rank support is required), which allows for an encoding with a smaller redundancy term compared to the general case.

We also use the Elias–Fano encoding for representing monotonic sequences:

2 and 3 can be further refined to optimise the leading constants, but this introduces clutter and does not improve our final result.

Throughout the paper, the space of a structure is almost always obtained by summing entropy-like bounds of the form \(k_i \log(U_i/k_i)\) coming from the two encodings above. To handle such sums uniformly, we will rely on the following inequality.

3 Reducing a Query to Two Candidates↩︎

The first step of the construction reduces the query rectangle to comparing two points. Since storing enough information to compare arbitrary pairs is far too expensive, the reduction must produce points with some additional structure.

By applying the above preprocessing, the RMQ problem is reduced to comparing the two mutually visible points \(p\) and \(q\), called candidates, and returning the heavier one.

In principle, the ability to compare arbitrary pairs of points would reveal the total order of all \(mn\) entries and thus requires \(\Omega(mn \log (mn))\) bits of space. The visibility condition provides the additional structure that makes the comparison problem compressible. The rest of the paper is therefore concerned only with comparing mutually visible pairs of points.

4 Active Points and Origins↩︎

We now introduce the main concepts of the data structure, and formulate exactly which pairs of points are going to be comparable by it. We then show that the pair of candidates produced by 5 satisfies the requirement.

4.0.0.1 Tree on columns.

Let \(\mathcal{T}\) be a complete binary tree over the columns \([1 \mathinner{.\,.}n]\). Each leaf of \(\mathcal{T}\) corresponds to a column, with the leaves ordered from left to right. Every node \(u \in \mathcal{T}\) corresponds to an interval, denoted as \(\mathop{\mathrm{span}}(u) \subseteq [1 \mathinner{.\,.}n]\), consisting of the columns of the leaves in the subtree of \(u\). In particular, the interval of the root is the whole \([1 \mathinner{.\,.}n]\), and the intervals of the two children of an internal node partition the interval of their parent into two parts of almost equal length. The depth of \(u\) in \(\mathcal{T}\) is denoted as \(\mathop{\mathrm{depth}}(u)\), where the root has depth \(1\).

The notion of active points is useful because ‘activeness’ behaves monotonically down the tree: once a point is active in some node, it remains active on the path toward its column leaf.

The next lemma gives a more algorithmic characterization of co-activity. Although the definition only requires the existence of some witness node in which both points are active, one can always pick a canonical one: the deeper of the two origins.

It can be directly verified that the pairs produced by the reduction of 5 are co-active.

In the remainder of the paper, we focus on encodings capable of efficiently comparing precisely the co-active pairs of points. Combined with the preprocessing of 5, which reduces every RMQ query to such a comparison by 8, this yields the main result.

5 Comparing Co-Active Pairs↩︎

From this point onward, we consider the following comparison problem: given two co-active points \(p_0\) and \(q_0\), determine which of them is heavier. We work with its decision version, fixing the hypothesis \(\mathcal{H} : w(p_0) \le w(q_0)\), so that the answer is \(q_0\) if \(\mathcal{H}\) holds, and \(p_0\) otherwise.

At a high level, the query algorithm maintains a co-active pair of points, initially \((p_0, q_0)\), along with the invariant that the hypothesis ‘the first point is no heavier than the second’ is equivalent to \(\mathcal{H}\). At each step, one of the two current points gets replaced by a substitute whose origin in \(\mathcal{T}\) is strictly closer to the root, in such a way that the invariant is preserved. Note that this strategy does not preserve the identity of the heavier point of the pair. The process terminates once a single local comparison can resolve the query.

5.1 Local Primitives↩︎

We now state the two local primitives that support the process described above; their implementation is deferred to 6. The first primitive is a ranking structure: given a set of points, it answers rank queries among them, and is used to perform the single comparison that resolves the query at the end of the process. The second primitive is a lifting structure: it takes a point and returns a suitable substitute whose origin is closer to the root of \(\mathcal{T}\), and is used to carry out the intermediate replacement steps.

5.1.0.1 Ranks of points.

For a set of points \(L\) and a point \(p \in L\), we define the rank of \(p\) in \(L\) as the number of points in \(L\) not heavier than \(p\). In particular, knowing the ranks of two points in \(L\) immediately tells us which of them is heavier.

The intended use of [lem:rank-primitive] is simple: if we have built the encoding for some subset \(L\subseteq A_{u}\) and both points of the current pair happen to lie in \(L\), the decision problem can be resolved immediately by comparing their ranks in \(L\).

5.1.0.2 Predecessors and successors.

For a set of points \(V\) and a point \(p\), the predecessor of \(p\) in \(V\) is the heaviest point in \(\left\lbrace q\in V : w(q) \le w(p) \right\rbrace\), and the successor of \(p\) in \(V\) is the lightest point in \(\left\lbrace q\in V : w(p) \le w(q) \right\rbrace\). If the first set is empty, the predecessor is defined to be \(\bot\), and if the second set is empty, the successor is defined to be \(\top\), whose weights are understood to be \(-\infty\) and \(+\infty\), respectively.

Thus, provided that the other point belongs to the target set, one may replace one of the current points with an appropriate predecessor or successor, while preserving the invariant.

The remainder of the paper is devoted to choosing suitable sets for [lem:rank-primitive,lem:lift-primitive]. The warm-up structure uses one lifting set per node of \(\mathcal{T}\) and therefore raises the origin by one or more levels at a time. The faster structure stores several such sets, organised by a tree over the depth range of \(\mathcal{T}\).

5.2 The Baseline Structure↩︎

We first describe a simpler \(\mathcal{O}(mn(\log m + \log\log n))\)-bit encoding with \(\mathcal{O}(\log n)\) query time before we move to the full trade-off.

5.2.0.1 Stored structures.

For every point \(p\), we store \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\). Note that \(\mathop{\mathrm{orig}}(p)\) is uniquely determined by \(\mathop{\mathrm{col}}(p)\) and \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\), as it is the unique node of \(\mathcal{T}\) at that depth whose interval contains \(\mathop{\mathrm{col}}(p)\), by 6. We assume standard constant-time navigation in \(\mathcal{T}\), which can be implemented with bitwise operations.

For every node \(u \in \mathcal{T}\), we define \(S_{u}\) as the set of points in \(A_{u}\) whose origin is \(u\) itself, and \(T_{u}\) as those whose origin is a strict ancestor of \(u\); by 6, these two sets partition \(A_{u}\). For each such node \(u\), we store the following two structures:

• by [lem:rank-primitive], a local ranking structure for the set \(S_{u}\), and

• by [lem:lift-primitive], a lifting structure with source set \(S_{u}\) and target set \(T_{u}\).

The idea is as follows. If the two current points have the same origin \(u\), then both belong to \(S_{u}\), and the ranking structure stored for \(u\) resolves the comparison. Otherwise, let \(u\) be the deeper of the two origins; then the corresponding point belongs to \(S_{u}\), while the other point is also active in \(u\) with its origin strictly above, and hence belongs to \(T_{u}\). In this case, the lifting structure stored for \(u\) is used. We now formalize this.

5.2.0.2 Query algorithm.

Let \(R\) be the query rectangle. Using 5, we obtain two candidate points \(p_0, q_0\in R\) such that \(\max_w(R)\) is the heavier of the two. By 8, the pair \((p_0, q_0)\) is co-active. We fix the hypothesis \(\mathcal{H} : w(p_0) \le w(q_0)\) and maintain an ordered pair \((p,q)\), initially \((p_0, q_0)\), with the invariant that the statement \(w(p) \le w(q)\) is equivalent to \(\mathcal{H}\).

If \(\mathop{\mathrm{orig}}(p) = \mathop{\mathrm{orig}}(q) = u\), then \(p, q\in S_{u}\), and the ranking structure stored for \(u\) resolves the comparison immediately. From now on assume that the two origins are different.

Suppose first that \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(q)) > \mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\), and let \(u \mathrel{\vcenter{:}}= \mathop{\mathrm{orig}}(q)\). By 7, we have \(p \in A_{u}\), and hence \(p \in T_{u}\). In this case we use the lifting structure stored for \(u\) to obtain \(q'\), the predecessor of \(q\) in \(T_{u}\). By the invariant, the statement \(w(p)\le w(q)\) is equivalent to \(\mathcal{H}\), and since \(p\in T_{u}\), 2 tells us that the same holds for \(w(p)\le w(q')\). At this point, either \(q'=\bot\), in which case the hypothesis is false and the query is resolved immediately, or else \(q'\in T_{u}\), and we replace \(q\) with \(q'\). In the latter case, the origin of \(q'\) lies strictly above \(u\), thus the origin of the deeper point has moved upward. Also, since both \(p\) and \(q'\) belong to \(A_{u}\), the new pair \((p,q')\) is again co-active.

The case \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p)) > \mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(q))\) is symmetric: we now take \(u \mathrel{\vcenter{:}}= \mathop{\mathrm{orig}}(p)\), and use the lifting structure stored for \(u\) to replace \(p\) with its successor \(p'\) in \(T_{u}\), where \(q\in T_{u}\) by 7. As before, 2 preserves the invariant, and the two possible outcomes mirror those of the previous case: either \(p'=\top\), which resolves the query, or we get a substitute point \(p'\in T_{u}\), with origin strictly above \(u\), and a new co-active pair \((p', q)\).

The algorithm continues in this way until the two current points have the same origin, at which point the ranking structure finishes the comparison. Since the height of \(\mathcal{T}\) is \(\mathcal{O}(\log n)\), there can be at most \(\mathcal{O}(\log n)\) such steps, and all work performed in each step is constant-time. Hence the total query time is \(\mathcal{O}(\log n)\).

5.2.0.3 Space analysis.

Most of the space analysis is taken care of by the following lemma, which we state as a self-contained bound. Its statement is tailored to match the per-node space bound of [lem:rank-primitive,lem:lift-primitive], so that applying it reduces to verifying that the relevant families of sets are pairwise disjoint. Isolating the statement in this way also lets us reuse the same bound later in the space analysis of the full structure.

We now sum the space over all components. For every point \(p\), the value \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\) belongs to \([1\mathinner{.\,.}H]\), where \(H=\mathcal{O}(\log n)\) is the height of \(\mathcal{T}\), and thus can be stored in \(\mathcal{O}(\log\log n)\) bits per point, for a total of \(\mathcal{O}(mn\log\log n)\) bits.

Next, we bound the total space of the local ranking structures. For every node \(u\in\mathcal{T}\) with \(S_{u}\neq\emptyset\), we store one such structure on the set \(S_{u}\), and its per-node cost, given by [lem:rank-primitive], coincides exactly with the one assumed in 9 (with \(X_u=S_{u}\)). Since every point has exactly one origin, the family \(\{S_{u} : u\in\mathcal{T}\}\) partitions the set of all points, and in particular is pairwise disjoint. Hence 9 applies and bounds the total space of the ranking structures by \(\mathcal{O}(mn\log m + mn\log\log n)\) bits.

The same argument applies to the lifting structures: each is built on \(S_{u}\) as its source set, and the per-node bound in [lem:lift-primitive] is identical to that of [lem:rank-primitive]. Their total space is therefore also \(\mathcal{O}(mn\log m + mn\log\log n)\) bits.

Finally, the reduction structure of 5 uses \(\mathcal{O}(mn\log m)\) bits, which completes the proof, as all components fit within \(\mathcal{O}(mn(\log m + \log\log n))\) bits of space.

5.3 The Full Structure↩︎

We now describe the general construction achieving the trade-off from 1. As in the baseline structure, the query algorithm fixes a comparison hypothesis and repeatedly replaces one of the two current points. The difference is that we no longer move one level of depth at a time in the tree \(\mathcal{T}\). Instead, we group consecutive depths of \(\mathcal{T}\) into larger blocks, and each lifting step moves the deeper point from its current block into an earlier one. The local ranking structures are also adapted: rather than comparing only points with exactly the same origin, they compare points whose origins lie in one prescribed depth block. As in the baseline structure, we store \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\) for every point \(p\).

5.3.0.1 Tree on depths.

Fix a parameter \(\kappa\in[1,\log\log n]\) and let \(\tau \mathrel{\vcenter{:}}= \lceil\log^{1/\kappa}n\rceil.\) Recall that the height of the complete binary tree \(\mathcal{T}\) is \(H=\mathcal{O}(\log n)\). We build a complete \(\tau\)-ary tree \(\mathcal{D}\) over the depths \([1\mathinner{.\,.}H]\) by recursively partitioning every interval into at most \(\tau\) consecutive sub-intervals of almost equal lengths, with the children of every node ordered so that smaller depths lie to the left. For every node \(x\in\mathcal{D}\), let \(\mathop{\mathrm{span}}(x)\subseteq[1\mathinner{.\,.}H]\) denote the depth interval represented by \(x\). The height of \(\mathcal{D}\) is \(\mathcal{O}(\kappa)\).

The tree \(\mathcal{D}\) is an auxiliary structure used to organise the query process. We assume standard constant-time navigation in both \(\mathcal{D}\) and \(\mathcal{T}\), which can be implemented with bitwise operations (for \(\mathcal{D}\) this requires rounding up \(\tau\) to the nearest power of two).

Given two points, their origin depths determine two leaves of \(\mathcal{D}\), and hence their lowest common ancestor node, whose children separate them. The algorithm will work relative to this one node of \(\mathcal{D}\): it repeatedly moves the deeper origin across its children until both current origin depths lie in the interval of the same child. At that point a local ranking structure finishes the comparison.

5.3.0.2 Ranking structures.

For every depth \(d\in[1\mathinner{.\,.}H]\), let \(C_d\) denote the largest canonical interval of \(\mathcal{D}\) of the form \([a\mathinner{.\,.}d]\), where an interval is canonical if it appears as \(\mathop{\mathrm{span}}(x)\) for some node \(x\in\mathcal{D}\). Now let \(u\in\mathcal{T}\) be any node of depth \(d\). We define \[L_{u} \mathrel{\vcenter{:}}= \left\lbrace p\in A_{u} : \mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\in C_d \right\rbrace.\] For every node \(u\in\mathcal{T}\), we store one local ranking structure of [lem:rank-primitive] for the set \(L_{u}\).

5.3.0.3 Lifting structures.

We next describe the lifting structures. Let \(y\) be a non-leftmost child of a node \(x\in\mathcal{D}\). If we denote \(\mathop{\mathrm{span}}(x)=[a\mathinner{.\,.}b]\) and \(\mathop{\mathrm{span}}(y)=[a'\mathinner{.\,.}b']\), then the depths lying in child intervals of \(x\) strictly to the left of \(y\) are precisely those in \([a\mathinner{.\,.}a'-1]\).

Now let \(u\in\mathcal{T}\) be a node such that \(\mathop{\mathrm{depth}}(u)\in\mathop{\mathrm{span}}(y)\). We define \[T_{y,u} \mathrel{\vcenter{:}}= \left\lbrace p\in A_{u} : \mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\in [a\mathinner{.\,.}a'-1] \right\rbrace.\] In words, \(T_{y,u}\) consists of the points that are active in \(u\), whose origin depths lie in one of the intervals of the left siblings of \(y\). For every such pair \((y,u)\), we store a lifting structure of [lem:lift-primitive] with source set \(S_{u}\) (the points with origin \(u\)) and target set \(T_{y,u}\).

This is a natural generalisation of the baseline structure: instead of lifting a point with origin \(u\) from \(\mathop{\mathrm{depth}}(u)\) to any smaller depth, we now lift it only into the union of the child intervals of \(x\) that lie to the left of the one currently containing \(\mathop{\mathrm{depth}}(u)\). In particular, for a fixed node \(u\in\mathcal{T}\), the sets \(T_{y,u}\) partition the set \(T_{u}\) (points active in \(u\) whose origins lie strictly above \(u\)) according to the first branching node in \(\mathcal{D}\) at which their origin depths diverge.

5.3.0.4 Query algorithm.

Let \(R\) be the query rectangle. As before, 5 returns two candidate points \(p_0,q_0\in R\), and 8 guarantees that this pair is co-active. We fix the hypothesis \(\mathcal{H} : w(p_0)\le w(q_0)\) and maintain an ordered pair \((p,q)\), initially \((p_0,q_0)\), with the same invariant as in the baseline structure.

If the two initial points have the same origin \(u\), then both belong to \(L_{u}\), since both are in \(A_{u}\) and \(\mathop{\mathrm{depth}}(u)\in C_{\mathop{\mathrm{depth}}(u)}\). Hence the ranking structure stored for \(u\) compares them immediately. Assume from now on that the current origins are different.

The two origin depths determine two leaves of \(\mathcal{D}\). Let \(x\in\mathcal{D}\) be the lowest common ancestor of these two leaves, and let \(y_p\) and \(y_q\) be the children of \(x\) containing \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\) and \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(q))\), respectively; see 1 for an illustration. Since the child intervals of \(x\) are consecutive depth ranges, the origin that lies in the rightmost of these two children is the deeper one. We stress that \(x\) remains fixed for the rest of the query: the target sets \(T_{y,u}\) are defined so that the origin depths of the two current points never leave \(\mathop{\mathrm{span}}(x)\), and hence the node \(x\) never needs to be recomputed.

Suppose first that \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(q)) > \mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\). Equivalently, \(y_q\) lies strictly to the right of \(y_p\). Let \(u \mathrel{\vcenter{:}}= \mathop{\mathrm{orig}}(q)\). By 7, we have \(p \in A_{u}\), and since \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\) lies in a child interval of \(x\) strictly to the left of \(y_q\), by the definition of \(T_{y_q,u}\), we have \(p\in T_{y_q,u}\).

We now use the lifting structure stored for \((y_q,u)\) to obtain \(q'\), the predecessor of \(q\) in \(T_{y_q,u}\). Since \(p\in T_{y_q,u}\), 2 tells us that \(w(p)\le w(q')\) is equivalent to \(w(p)\le w(q)\), and hence to \(\mathcal{H}\). At this point, three cases may occur.

(i) If \(q'=\bot\), then the current hypothesis is false, and the query is resolved immediately.

(ii) If \(q'\neq\bot\) and the child \(y_{q'}\) of \(x\) containing \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(q'))\) is different from \(y_p\), then we replace \(q\) with \(q'\) and continue. Since \(p, q' \in A_{u}\), the new pair \((p,q')\) is again co-active.

(iii) If \(q'\neq\bot\) and \(y_{q'}=y_p\), then this is the last lifting step, and it remains to compare \(p\) and \(q'\). Let \(\mathop{\mathrm{span}}(y_p)=[a\mathinner{.\,.}b]\). Since \(q'\) was obtained from the lifting structure stored at \(u=\mathop{\mathrm{orig}}(q)\), both \(p\) and \(q'\) are active in \(u\). Moreover, \(\mathop{\mathrm{depth}}(u)\in \mathop{\mathrm{span}}(y_q)\) and \(y_q\) lies strictly to the right of \(y_p\), so \(\mathop{\mathrm{depth}}(u)>b\). Let \(v\) be the ancestor of \(u\) at depth \(b\). By 6, both \(p\) and \(q'\) are active in \(v\).

  The origin depth of $p$ belongs to $\mathop{\mathrm{span}}(y_p)$
  by definition of $y_p$, and the origin depth of $q'$ belongs to
  $\mathop{\mathrm{span}}(y_p)$ because $y_{q'}=y_p$. Since
  $\mathop{\mathrm{span}}(y_p)$ is a canonical interval ending at
  $b$, we have $\mathop{\mathrm{span}}(y_p)\subseteq C_b$. Hence
  both points belong to $L_{v}$, and the ranking structure stored
  for $v$ compares them in constant time.

The case in which \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p)) > \mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(q))\), or equivalently, when \(y_p\) lies strictly to the right of \(y_q\), is symmetric: we take \(u \mathrel{\vcenter{:}}= \mathop{\mathrm{orig}}(p)\), and use the lifting structure stored for \((y_p,u)\) to replace \(p\) with its successor \(p'\) in \(T_{y_p,u}\), where \(q \in T_{y_p,u}\) by a symmetric argument. As before, 2 preserves the invariant, and the three possible outcomes mirror those of the previous case. If \(p' = \top\), the hypothesis is false and the query is resolved immediately. Otherwise, if the child \(y_{p'}\) of \(x\) containing \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p'))\) differs from \(y_q\), we continue with the new co-active pair \((p', q)\). Finally, if \(y_{p'} = y_q\) and \(\mathop{\mathrm{span}}(y_q) = [a \mathinner{.\,.}b]\), we use the ranking structure stored for the ancestor of \(u\) at depth \(b\) and compare \(p'\) and \(q\) in constant time.

Each nonterminal lifting step preserves the truth of the current hypothesis and strictly decreases the child index of the deeper of the two current origins among the children of the fixed node \(x\in\mathcal{D}\) (even though which of the two origins is deeper may alternate between steps). Since \(x\) has at most \(\tau\) children, at most \(\tau-1\) such steps are possible before the algorithm terminates. Every step takes constant time, so the total query time is \(\mathcal{O}(\tau)=\mathcal{O}(\log^{1/\kappa}n)\).

5.3.0.5 Space analysis.

As in the baseline structure, the bulk of the argument relies on 9. The new complication is that the families of sets are no longer globally pairwise disjoint. To recover disjointness, we partition the stored structures into \(\mathcal{O}(\kappa)\) groups, one per level of \(\mathcal{D}\), so that within each group the relevant sets are pairwise disjoint. 9 then applies separately on each group, and summing over the \(\mathcal{O}(\kappa)\) levels of \(\mathcal{D}\) yields the claimed bound.

We begin with the local ranking structures. For every node \(u\in\mathcal{T}\), the ranking structure stored for \(u\) is built for the set \(L_{u}\), and its per-node cost, given by [lem:rank-primitive], coincides with the one assumed in 9 (with \(X_u=L_{u}\)). Recall that \(L_{u}\) consists of the points in \(A_{u}\) whose origin depth falls in \(C_d\), the largest canonical interval of \(\mathcal{D}\) ending at \(d=\mathop{\mathrm{depth}}(u)\).

We group the stored ranking structures by the level of \(\mathcal{D}\) at which \(C_d\) appears, that is, by the level of the unique \(\mathcal{D}\)-node whose span is \(C_d\). Fix one level \(\ell\), and consider all nodes \(u\in\mathcal{T}\) for which \(C_{\mathop{\mathrm{depth}}(u)}\) appears at level \(\ell\). We claim that the corresponding sets \(L_{u}\) are pairwise disjoint. Indeed, suppose that a point \(p\) belonged to both \(L_{u}\) and \(L_{v}\). Then \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\) would lie in \(C_{\mathop{\mathrm{depth}}(u)}\cap C_{\mathop{\mathrm{depth}}(v)}\), and since canonical intervals appearing at the same level of \(\mathcal{D}\) are pairwise disjoint, this forces \(C_{\mathop{\mathrm{depth}}(u)}=C_{\mathop{\mathrm{depth}}(v)}\), and in turn \(\mathop{\mathrm{depth}}(u)=\mathop{\mathrm{depth}}(v)\) because each \(C_d\) ends at \(d\). Now \(p\) is active in both \(u\) and \(v\), with the same depth in \(\mathcal{T}\), so 6 gives \(u=v\), proving the claim.

9 therefore applies and bounds the total space of the ranking structures associated with level \(\ell\) by \(\mathcal{O}(mn(\log m+\log\log n))\) bits. Summing over the \(\mathcal{O}(\kappa)\) levels of \(\mathcal{D}\), all ranking structures together use \(\mathcal{O}(\kappa mn(\log m+\log\log n))\) bits.

We now turn to the lifting structures. Recall that for every non-leftmost child \(y\) of a node \(x\in\mathcal{D}\), and every node \(u\in\mathcal{T}\) with \(\mathop{\mathrm{depth}}(u)\in\mathop{\mathrm{span}}(y)\), we store one lifting structure with source set \(S_{u}\) and target set \(T_{y,u}\). The per-node space bound of [lem:lift-primitive] depends only on the source set and coincides with the one assumed in 9 (with \(X_u=S_{u}\)).

Here the situation differs from the ranking case. The source sets \(\left\lbrace S_{u} : u\in\mathcal{T} \right\rbrace\) already partition the set of all points; what prevents a direct application of 9 is that each \(S_{u}\) is reused as the source set of several stored lifting structures. We claim that each \(S_{u}\) appears as a source set at most \(\kappa\) times. Indeed, \(S_{u}\) is the source set of the structure stored for a pair \((y,u)\) only when \(y\) is a node of \(\mathcal{D}\) with \(\mathop{\mathrm{depth}}(u)\in\mathop{\mathrm{span}}(y)\), and there are \(\kappa\) such nodes, as each is an ancestor of the leaf corresponding to \(\mathop{\mathrm{depth}}(u)\).

We group the stored lifting structures by the level of \(\mathcal{D}\) containing \(y\). By the observation above, each \(S_{u}\) appears as the source set of at most one structure per group, so the source sets within a group are pairwise disjoint. 9 therefore bounds the total space of the group by \(\mathcal{O}(mn(\log m+\log\log n))\) bits. Summing over the \(\mathcal{O}(\kappa)\) levels of \(\mathcal{D}\), all lifting structures together use \(\mathcal{O}(\kappa mn(\log m+\log\log n))\) bits.

As in the baseline structure, storing \(\mathop{\mathrm{depth}}(\mathop{\mathrm{orig}}(p))\) for every point uses \(\mathcal{O}(mn\log\log n)\) bits, and the reduction structure of 5 uses \(\mathcal{O}(mn\log m)\) bits. Hence the entire structure takes \(\mathcal{O}(\kappa mn(\log m+\log\log n))\) bits, as promised. This concludes the proof of 1.

6 Construction of Local Primitives↩︎

We now describe the construction of the two local primitives stated in [lem:rank-primitive,lem:lift-primitive]. Both constructions are entirely local to one fixed node of \(\mathcal{T}\), and rely on a common decomposition of the active set into at most \(4m\) ‘monotone’ subsets, called quarter-rows. They also make use of the two succinct encodings for sparse sets and monotone sequences introduced in [lem:sparse,lem:mono]. The lifting structure uses the ranking structure as one of its sub-components, so we present the ranking primitive first and then build the lifting primitive on top of it.

6.0.0.1 Local coordinates.

Throughout this section we fix one node \(u\in\mathcal{T}\) and denote \[\mathop{\mathrm{span}}(u)=[a\mathinner{.\,.}b] \qquad\text{and}\qquad \lambda \mathrel{\vcenter{:}}= |\mathop{\mathrm{span}}(u)| = b-a+1.\] For every point \(p\in [1\mathinner{.\,.}m]\times \mathop{\mathrm{span}}(u)\), we define its local column in \(u\) by \[\mathop{\mathrm{col}}_u(p)\mathrel{\vcenter{:}}= \mathop{\mathrm{col}}(p)-a+1 \in [1\mathinner{.\,.}\lambda].\] From this point onward, we will view columns through their local coordinates inside \(\mathop{\mathrm{span}}(u)\).

We assume that the 1D RMQ structures of 1 have been built for all rows, and we will use them only to test, in constant time, whether a point is visible from a given column.

6.0.0.2 Quarter-rows.

We describe a canonical decomposition of \(A_{u}\) into quarter-rows that underlies both local structures. If \(u\) is a leaf, \(A_{u}=[1\mathinner{.\,.}m]\times\{j\}\) for a single column \(j\), and we define the \(m\) quarter-rows to be the singletons \(\{(i,j)\}\) for \(i\in[1\mathinner{.\,.}m]\); all claims below are immediate in this case, so assume \(u\) is internal, with children covering the intervals \([a_1\mathinner{.\,.}b_1]\) and \([a_2\mathinner{.\,.}b_2]\).

For any \(p\in A_{u}\), the column \(\mathop{\mathrm{col}}(p)\) belongs to exactly one of these two child intervals. Since \(p\) is active in \(u\), it is visible from some column in \(\partial u = \{a_1,b_1,a_2,b_2\}\), and by monotonicity of visibility along its row, \(p\) is also visible from at least one endpoint of the child interval that contains \(\mathop{\mathrm{col}}(p)\). We assign \(p\) a canonical endpoint: the left endpoint of the child interval containing \(\mathop{\mathrm{col}}(p)\) if \(p\) is visible from it, and its right endpoint otherwise. For each pair \((i,c) \in[1\mathinner{.\,.}m] \times \{a_1,b_1,a_2,b_2\}\), the corresponding quarter-row is the set of all points in \(A_{u}\) in row \(i\) whose canonical endpoint is \(c\); we write \(Q_u(p)\) for the quarter-row containing \(p\).

This partitions \(A_{u}\) into at most \(4m\) quarter-rows. Given \(p\), the quarter-row \(Q_u(p)\) can be identified using \(\mathcal{O}(\log m)\) bits in \(\mathcal{O}(1)\) time by locating the child interval containing \(\mathop{\mathrm{col}}(p)\) and testing visibility from its endpoints using 1.

We are now ready to prove the two local primitives of [lem:rank-primitive,lem:lift-primitive], starting with [lem:rank-primitive], which we restate below.

We now proceed with the proof of [lem:lift-primitive], restated below.

References↩︎