Range Longest Increasing Subsequence and Its Relatives

The first problem is the 1D range longest increasing subsequence problem ($\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$). In the $\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem, we are given as input a sequence $𝒮=(a_1,a_2,\mathrm{\dots },a_n)$ of $n$ real numbers and a collection $𝒬$ of $m$ query ranges, where each $q\in 𝒬$ is a range (or an interval) $[x_1,x_2]\subseteq [1,n]$. For each $q=[x_1,x_2]\in 𝒬$, the goal is to report the $\mathrm{𝖫𝖨𝖲}$ of the sequence $𝒮\cap [x_1,x_2]=(a_{x_1},a_{x_1+1}\mathrm{\dots },a_{x_2-1},a_{x_2})$ (i.e., the output must be the longest increasing subsequence in $𝒮\cap [x_1,x_2]$). The length of the $\mathrm{𝖫𝖨𝖲}$ of the sequence $𝒮\cap q$ is denoted by $\mathrm{𝖫𝖨𝖲}(𝒮\cap q)$. Throughout the paper, we abuse notation for simplicity by using $\mathrm{𝖫𝖨𝖲}$ to refer to both the subsequence and its length. We clarify the intended meaning wherever it may be unclear.

A straightforward approach to solve the $\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem would involve no preprocessing: for each range $[x_1,x_2]$ in $𝒬$, we will retrieve the elements $a_{x_1},a_{x_1+1}\mathrm{\dots },a_{x_2-1},a_{x_2}$ and report their $\mathrm{𝖫𝖨𝖲}$. This would require $\mathrm{\Omega }(mn\log n)$ time in the worst-case (for instance when many of the ranges in $𝒬$ are of $\mathrm{\Omega }(n)$ length). In a remarkable work, Tiskin [74, 76, 75] broke the quadratic barrier, by designing an $O((n+m)\log n)$ time algorithm, albeit for the computationally easier length version of the $\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem, in which for all $q\in 𝒬$, the goal is to only output the length of the $\mathrm{𝖫𝖨𝖲}$ in the range $q$ (i.e., $\mathrm{𝖫𝖨𝖲}(𝒮\cap q)$). While the algorithm designed by Tiskin is tailored to handle the length version of the $\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem, in a subsequent work to the current paper, Gawrychowski, Gorbachev, and Kociumaka [29] extend Tiskin’s algorithm to handle the reporting version as well by providing an algorithm which answers the reporting version of the $\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem in $O(n{(\log n)}^3+m+k)$ time.

Since the vanilla version of the range $\mathrm{𝖫𝖨𝖲}$ problem is completely understood (up to log factors), we focus on the following three variants.

The next problem is the 2D range longest increasing subsequence problem ($\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$) which is a natural generalization of the $\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem. As before, we are given as input a sequence $𝒮=(a_1,a_2,\mathrm{\dots },a_n)$. Consider a mapping where the $i^{\text{th}}$ element $a_i\in 𝒮$ is mapped to a 2D point $p_i=(i,a_i)$. Let $𝒫=\{p_1,p_2,\mathrm{\dots },p_n\}$ be a collection of these $n$ points. We are also given as input a collection $𝒬$ of $m$ query ranges, where each range in $𝒬$ is an axis-aligned rectangle in 2D. For each $q\in 𝒬$, the goal is to report the $\mathrm{𝖫𝖨𝖲}$ of $𝒫\cap q$, i.e., the points of $𝒫$ lying inside $q$. See Figure 1(a) for an example.

Once again the naive approach to solve the problem would take $O(mn\log n)$ time, where for each range $q\in 𝒬$, we will scan the points in $𝒫$ to filter out the points lying inside $q$ and then compute their $\mathrm{𝖫𝖨𝖲}$. One might be tempted to use orthogonal range searching data structures [3, 5, 24, 56, 13] to efficiently report $𝒫\cap q$, but in the worst-case we could have many queries with $|𝒫\cap q|=\mathrm{\Omega }(n)$. In this paper, even for the $\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem, we succeed to improve on the basic quadratic runtime algorithm when $m$ is roughly $\mathrm{\Omega }(\sqrt{n})$. We obtain the following result where the $\tilde{O}(\cdot )$ notation hides polylog factors.

In the geometric data structures literature, colored range searching [41, 57, 59, 54, 45, 40, 14, 6, 34, 37, 46, 55, 71, 33] is a well-studied generalization of traditional range searching problems. In the colored setting, the geometric objects are partitioned into disjoint groups (or colors), and given a query region $q$, the typical goal is to efficiently report [22, 25, 23, 47], or count [39], or approximately count [60] the number of colors intersecting $q$, or find the majority color inside $q$ [21, 44].

In the same spirit, we study the colored 1D range longest increasing subsequence problem ($\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$). In addition to the sequence $𝒮$ and 1D range queries $𝒬$ given as input to the $\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem, in the $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem we are additionally given a coloring of $𝒮$ using the color set $𝒞$. Each element $a_i\in 𝒮$ has a color chosen from $𝒞$ (the corresponding 2D point $p_i$ also has the same color). For all $c\in 𝒞$, let ${𝒫}_c\subseteq 𝒫$ denote the set of points with color $c$ and for any $q\in 𝒬$, with a slight abuse of notation, we will use $\mathrm{𝖫𝖨𝖲}({𝒫}_c\cap q)$ to denote the length of the $\mathrm{𝖫𝖨𝖲}$ of ${𝒫}_c\cap q$. Moreover, we say a subsequence is monochromatic, if all the elements in the subsequence have the same color. For each $q\in 𝒬$, the goal is then to report the longest monochromatic increasing subsequence whose length is equal to $\underset{c\in C}{\max }\mathrm{𝖫𝖨𝖲}({𝒫}_c\cap q)$. See Figure 1(b) for an example in 2D. We obtain the following result.

We complement the above result with a conditional lower bound that indicates that the above runtime for $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ might be (near) optimal.

The Combinatorial Boolean Matrix Multiplication Hypothesis ($\mathrm{𝖢𝖡𝖬𝖬𝖧}$) roughly asserts that Boolean matrix multiplication of two $\sqrt{n}\times \sqrt{n}$ matrices cannot be computed by any combinatorial algorithm running in time $n^{1.5-\epsilon }$, for any constant $\epsilon >0$. Here “combinatorial algorithm” is typically defined as “non-Strassen-like algorithm” (as defined in [12]), and this captures all known fast matrix multiplication algorithms.

While $\mathrm{𝖢𝖡𝖬𝖬𝖧}$ is widely explored since the 1990s [70, 48], there is no strong consensus in the computer science community about its plausibility. In a recent breakthrough, Abboud et al. [1], have come tantalizingly close to even refuting it. All that said, $\mathrm{𝖢𝖡𝖬𝖬𝖧}$ remains a widely used hypothesis for proving conditional lower bounds [66, 2, 35]. At the very least, Theorem 3 provides evidence that any algorithm for $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ that is significantly faster than the runtime given in Theorem 2, must be highly non-trivial.

The proof of Theorem 3 follows as a simple consequence of a $\mathrm{𝖢𝖡𝖬𝖬𝖧}$ based conditional lower bound in [21] for computing the mode of a sequence subject to range queries.

The most general problem that we study in this paper is the colored 2D range longest increasing subsequence problem ($\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$). The queries in $𝒬$ will be axis-aligned rectangles. For each $q\in 𝒬$, the goal is then to report the longest monochromatic increasing subsequence which attains $\underset{c\in C}{\max }\mathrm{𝖫𝖨𝖲}({𝒫}_c\cap q)$. See Figure 1(b) for an example. We obtain the following result.

We remark that the conditional lower bound of Theorem 3 continues to hold here too.

In Table 1, we have summarized the state-of-the-art upper and (conditional) lower bounds for the various variants of $\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ discussed in this paper.

A natural data structure counterpart question to the aforementioned four problems is to design a data structure for these problems and measure the tradeoff in the time needed for preprocessing the input sequence versus the time needed to answer a single range query. In Table 2, we have summarized the preprocessing and query time bounds that can be derived from the proofs of Theorems 1, 2, and 4.

Finally, we note that the proof of Theorem 3 also implies that assuming $\mathrm{𝖢𝖡𝖬𝖬𝖧}$, for every $\epsilon >0$, there is no data structure for the reporting version of the $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem (or the $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem) which can be preprocessed using a combinatorial algorithm in $O(n^{1.5-\epsilon })$ time such that each query can be answered using a combinatorial algorithm in $\frac{k_q}{2}+O(n^{0.5-\epsilon })$ time.

Please refer to Figure 2(i) where eighteen points are shown. Chain $C_1$ and chain $C_2$ are increasing sequences to the left of $x^{\ast }$ and both have length four. Our first observation is that if we are allowed to store either $C_1$ or $C_2$, then it would be wiser to store $C_2$. The reason is that $C_2$ can “stitch” itself with chain $C_3$ and $C_4$, to form an increasing subsequence of length six and eight, respectively. On the other hand, $C_1$ cannot stitch itself with $C_3$ or $C_4$ to form a larger increasing subsequence. Analogously, between chains $C_4$ and $C_5$, we will prefer $C_4$ since it can stitch with $C_2$, whereas $C_5$ cannot stitch with any chain to the left of $x^{\ast }$. In fact, the $\mathrm{𝖫𝖨𝖲}$ of the eighteen points is realised by the chain $C_2\cup C_4$ with length eight. This motivates the definition of lowest peak and highest base.

For an increasing subsequence $S\in 𝒮$, we define peak (resp., base) to be the last (resp., first) element in $S$. The algorithm will store two $2$-dimensional arrays:

Array $L$:

For all integers $1\le x_1\le x^{\ast }$ and for all $1\le \alpha \le \tau$, among all increasing subsequences of length $\alpha$ in the range $[x_1,x^{\ast }]$, let $S$ be the subsequence with the lowest peak. Then $L[x_1][\alpha ]$ stores the value of the last element in $S$.

Array $R$:

For all integers and for all $1\le \beta \le \tau$, among all increasing sequences of length $\beta$ in the range $(x^{\ast },x_2]$, let $S$ be the subsequence with the highest base. Then $R[x_2][\beta ]$ stores the value of the first element in $S$.

For example, in Figure 2(i), for the range $[x_1,x^{\ast }]$ and $\alpha =4$, the chain $C_2$ is the subsequence with the lowest peak; and for $(x^{\ast },x_2]$ and $\alpha =4$, chain $C_4$ is the subsequence with the highest base. Efficient computation of the $O(n\tau )$ entries in arrays $L$ and $R$ will be discussed later.

A pair $(L[x_1][\alpha ],R[x_2][\beta ])$ is defined to be compatible if , i.e., it is possible to “stitch” the sequences corresponding to $L[x_1][\alpha ]$ and $R[x_2][\beta ]$ to obtain an increasing sequence of length $\alpha +\beta$. For a query range $q=[x_1,x_2]$, our goal is to find the compatible pair $(L[x_1][\alpha ],R[x_2][\beta ])$ which maximizes the value of $\alpha +\beta$, i.e.,

For a given query $q=[x_1,x_2]$, a naive approach is to inspect all pairs of the form $(L[x_1][\alpha ],R[x_2][\beta ])$, for all $1\le \alpha ,\beta \le \tau$, and then pick a compatible pair which maximizes the value of $\alpha +\beta$. The number of pairs inspected is $\mathrm{\Theta }({\tau }^2)$ which we cannot afford. However, the following monotone property will help in reducing the number of pairs inspected to $O(\tau \log \tau )$:

• $\mathrm{■}$

  For a fixed value of $x_1$, the value of $L[x_1][\alpha ]$ increases as the value of $\alpha$ increases, i.e., for any $1\le \alpha \le {\alpha }^{\prime }\le \tau$, we have $L[x_1][\alpha ]\le L[x_1][{\alpha }^{\prime }]$.

• $\mathrm{■}$

  Analogously, for a fixed value of $x_2$, the value of $R[x_2][\beta ]$ decreases as the value of $\beta$ increases, i.e., for any $1\le \beta \le {\beta }^{\prime }\le \tau$, we have $R[x_2][\beta ]\ge R[x_2][{\beta }^{\prime }]$.

See Figure 2(ii) for an example where $L[x_1][\alpha ]$ values are increasing with increase in $\alpha$ and $R[x_2][\beta ]$ values are decreasing with increase in $\beta$. For each $1\le i\le \tau$, the largest ${\beta }_i$ for which $(L[x_1][i],R[x_2][{\beta }_i])$ is compatible can be found in $O(\log \tau )$ time by doing a binary search on the monotone sequence $(R[x_2][1],R[x_2][2],\mathrm{\dots },R[x_2][\tau ])$. Finally, report ${\max }_i(i+{\beta }_i)$ as the length of the $\mathrm{𝖫𝖨𝖲}$ for $𝒮\cap q$. Overall, the time taken to answer the $m$ query ranges will be $O(m\tau \log \tau )$.

Now the key task is to design a preprocessing algorithm which can quickly compute each entry in the two-dimensional arrays $L$ and $R$. We will look at $R$ and an analogous discussion will hold for $L$. Assume that we have computed the value of $R[x_2-1][\beta ]$ and would like to next compute $R[x_2][\beta ]$. Let $p_{x_2}=(x_2,a_{x_2})$ be the point with $x$-coordinate $x_2$ which is encountered when we move the vertical line from $x_2-1$ to $x_2$.

Formally, we claim that the value of $R[x_2][\beta ]$ is higher than $R[x_2-1][\beta ]$ if and only if there is an increasing subsequence with the following three properties: (i) the subsequence length is $\beta$, (ii) the base of the subsequence is higher than $R[x_2-1][\beta ]$, and (iii) the last point in the subsequence is $p_{x_2}$. Please refer to Figure 3 for an example.

We define $p_{x_2}$ to be a pivot point. Now to efficiently compute $R[x_2][\beta ]$, we will need the support of another two-dimensional array $B$ defined as follows: among all increasing subsequences of length $\beta$ in the range $(x^{\ast },x_2]$ containing pivot point $p_{x_2}$ as the last element, let $S$ be the subsequence with the highest base. Then $B[x_2][\beta ]$ is defined to be the value of the first element in $S$. In Figure 3(a) and Figure 3(b), $B[x_2][5]$ is realized by the $y$-coordinate of $b$ and $c$, respectively. As a result, we can succinctly encode the three properties stated above as follows:

In other words, an increasing sequence of length $\beta$ in the interval $(x^{\ast },x_2]$ with the highest base will either contain the pivot element $p_{x_2}$ or not. The first term (i.e., $R[x_2-1][\beta ]$) captures the case where $p_{x_2}$ is not included, whereas the second term (i.e., $B[x_2][\beta ]$) captures the case where $p_{x_2}$ is included. As such, the task of efficiently computing $R$ has been reduced to the task of efficiently computing $B$.

The final step is to compute each entry in $B$ in polylogarithmic time. The entries will be computed in increasing values of $\beta$. Assume that the entries corresponding to sequences of length at most $\beta -1$ have been computed. Then the entries $B[x_2][\beta ]$’s can be reduced to entries of $B[\cdot ][\beta -1]$’s as follows:

We will efficiently compute $B[x_2][\beta ]$’s by constructing a data structure which can answer 2D range-max queries. In a 2D range-max query, we are given $n$ weighted points $𝒫$ in 2D. Each point is associated with a weight. For each point $p_i=(i,a_i)\in 𝒫$, given a query region of the form $q^{\prime }=(-\mathrm{\infty },i)\times (-\mathrm{\infty },a_i)$, the goal is to report the point in $𝒫\cap q^{\prime }$ with the maximum weight. The 2D range-max problem can be solved in $O(n\log n)$ time (via reduction to the so-called 2D orthogonal point location problem [69]).

Now with each point $p_i\in 𝒫$, we associate the weight $B[i][\beta -1]$ and build a 2D range-max data structure. For each point $p_{x_2}=(x_2,a_{x_2})\in 𝒫$, the point in $𝒫\cap (-\mathrm{\infty },x_2)\times (-\mathrm{\infty },a_{x_2})$ with the maximum weight is reported. If point $p_i$ is reported, then set $B[x_2][\beta ]=B[i][\beta -1]$. The correctness follows from the third case in the above dynamic programming. Since $\beta \le \tau$, the time taken to construct $B$ is $O(\tau )\times O(n\log n)=O(n\tau \log n)$.

Therefore, the overall time taken by this technique to answer $\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ will be $\tilde{O}(m\tau +n\tau )+O(k)=\tilde{O}(m\sqrt{n}+n\sqrt{n})+O(k)$ by setting $\tau \leftarrow \sqrt{n}$.

We briefly describe the challenge arising while handling $\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ where the queries are axis-parallel rectangles. The definition of highest bases and lowest peak fail to be directly useful. For example, see Figure 4, where $\mathrm{𝖫𝖨𝖲}(𝒫\cap q)$ is equal to five, and is realized by stitching $S_2$ and $S_3$. However, $L[x_1][3]$ will correspond to the sequence $S_1$ and $R[x_2][2]$ will correspond to the sequence $S_4$, both of which lie completely outside $q$.

The key observation in the 2D setting is that for an increasing subsequence $S$ and a query rectangle $q=[x_1,x_2]\times [y_1,y_2]$, if the first and the last point of $S$ lie inside $q$, then all the points of $S$ lie inside $q$. Accordingly, we generalize the definitions of $L$ and $R$. Specifically, in the 2D setting, $R$ takes two arguments, the query $q$ and an integer $\beta$, and is defined as follows:

For example, in Figure 4, the new definition of $R(q,2)$ ensures that the sequence $S_3$ gets captured instead of $S_4$. We construct $L$ analogously. Note that in the 1D setting, $L$ and $R$ were explicitly computed. However, in the 2D setting, the number of combinatorially different axis-parallel rectangles is significantly more than our time budget. Therefore, $L$ and $R$ cannot be precomputed and stored. Instead, for all $1\le \alpha \le \tau$ (resp., $1\le \beta \le \tau$), we will compute $L(q,\alpha )$ (resp., $R(q,\beta )$) during the query algorithm in $O(\tau \cdot \text{polylog }n)$ time.

One challenge with the $\mathrm{𝖫𝖨𝖲}$ problem is that it is not decomposable. Consider a query range $q=[x_1,x_2]\times (-\mathrm{\infty },+\mathrm{\infty })$ and an $x^{\ast }$ such that . Let $q_{\mathrm{\ell }}=[x_1,x^{\ast }]\times (-\mathrm{\infty },+\mathrm{\infty })$ and $q_r=(x^{\ast },x_2]\times (-\mathrm{\infty },+\mathrm{\infty })$ such that $q=q_{\mathrm{\ell }}\cup q_r$. Then the $\mathrm{𝖫𝖨𝖲}$ of $𝒫\cap q$ need not be the concatenation of the $\mathrm{𝖫𝖨𝖲}$ of $𝒫\cap q_{\mathrm{\ell }}$ and the $\mathrm{𝖫𝖨𝖲}$ of $𝒫\cap q_r$, since the rightmost point in the $\mathrm{𝖫𝖨𝖲}$ of $𝒫\cap q_{\mathrm{\ell }}$ might have a larger value than the leftmost point in the $\mathrm{𝖫𝖨𝖲}$ of $𝒮\cap q_r$.

However, suppose an oracle reveals that point $p_i\in 𝒫$ lies in the $\mathrm{𝖫𝖨𝖲}$ of range $q=[x_1,x_2]\times (-\mathrm{\infty },+\mathrm{\infty })$. Then we claim that the problem becomes decomposable. We will define some notation before proceeding. For a point $p_i=(i,a_i)\in 𝒫$ corresponding to an element $a_i\in 𝒮$, define the north-east region of $p_i$ as $NE(p_i)=\{(x,y)\mid x\ge i\text{ and }y\ge a_i\}$. Analogously, define the north-west, the south-west and the south-east region of $p_i$ which are denoted by $NW(p_i),SW(p_i)\text{ and }SE(p_i)$, respectively. Then it is easy to observe that,

See Figure 5 for an example. In other words, knowing that $p_i$ belongs to the $\mathrm{𝖫𝖨𝖲}$ decomposes the original $\mathrm{𝖫𝖨𝖲}$ problem into two $\mathrm{𝖫𝖨𝖲}$ sub-problems which can be computed independently. In such a case, we refer to point $p_i$ as a stitching element, which is formally defined below.

The goal of our algorithm is to:

Construct a small-sized set $ℛ\subseteq 𝒫$ such that, for any $q\in 𝒬$, at least one stitching element w.r.t. $q$ is contained in $ℛ\cap q$.

For each $p_i\in ℛ$, in the preprocessing phase, the two terms on the right hand side of equation 1 can be computed in $O(n\log n)$ time for all possible queries. Therefore, the preprocessing time will be $O(|ℛ|n\log n)$.

By using the fact that $\mathrm{𝖫𝖨𝖲}(𝒫\cap q)\ge \tau$, it is possible to construct a set $ℛ$ of size roughly $\frac{n\log n}{\tau }\approx \sqrt{n}\log n$ via random sampling. For each $1\le i\le n$, sample $p_i\in 𝒫$ independently with probability $\frac{c\log n}{\tau }$, where $c$ is a sufficiently large constant. Let $ℛ\subseteq 𝒫$ be the set of sampled points. Then we can establish the following connection between $ℛ$ and the stitching elements.

This ensures that the preprocessing time will be $O(|ℛ|n\log n)=O(n^{3/2}{\log }^{2}n)$. To answer any range $q$, first scan $ℛ$ to identify the points which lie inside $q$. For each element $p_i\in ℛ\cap q$, compute the right hand side of equation 1 in $O(\log n)$ time. Finally, report the largest value computed. Therefore, the query time is bounded by $O(|𝒬|\cdot |ℛ|\cdot \log n)=O(m\sqrt{n}{\log }^{2}n)$.

The $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem is more challenging than the $\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem. Firstly, the result of Theorem 1 does not really help in answering $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ since it completely ignores the information about the colors. Secondly, there might be a temptation to solve the problem “independently” for each color class. For example, consider a setting where each color class has roughly equal number of points, i.e., $n/|𝒞|$ points. Consider a color $c$ and build an instance of Theorem 1 based on the points of color $c$. Then, for each query $q\in 𝒬$, we have the value of $\mathrm{𝖫𝖨𝖲}({𝒫}_c\cap q)$. Repeat this for each color in $𝒞$. Finally, for each query $q\in 𝒬$, report the color $c$ for which $\mathrm{𝖫𝖨𝖲}({𝒫}_c\cap q)$ is maximized.

Now lets (informally) analyze this algorithm. The running time bound of Theorem 1 has three terms. For now, lets ignore the second term and the third term, which represent the time taken to build the data structure and the time taken to report the output of the $m$ queries. The first term is the time taken to answer $m$ queries (which is roughly $\sqrt{n}$ time per query). Adding the first term for each color class, we get

which is $\tilde{O}(mn)$ when $|𝒞|=\mathrm{\Theta }(n)$ and $\tilde{O}(m{n}^{\frac{1+\epsilon }{2}})\gg m\sqrt{n}$ when $|𝒞|=n^{\epsilon }$, for any . Therefore, in the worst-case this approach does not help achieve our target query time bound.

We will design a third technique which will be helpful to answer $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{1}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ and $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$. The key idea is to handle all the colors in a “combined” manner. The technique will work well when all the colors have small cardinality. Given a parameter $\mathrm{\Delta }$, assume that for each color $c$, the value of ${|𝒫|}_c\le \mathrm{\Delta }$. The key observations made by the algorithm are the following:

• $\mathrm{■}$

  Bounding the number of output subsequences. For a query $q$, let the output $\mathrm{𝖫𝖨𝖲}$ be $S$ of color $c$. Let $p_i\in {𝒫}_c$ (resp., $p_j\in {𝒫}_c$) be the first (resp., last) point on $S$. Call this a pair $(i,j)$. As such, whenever color $c$ is the output, the number of distinct pairs will be $O({|{𝒫}_c|}^2)$. Adding up over all the colors, the total number of distinct pairs will be:

  $$\sum _{c}O({|{𝒫}_c|}^2)\le O\left(\mathrm{\Delta }\sum _c|{𝒫}_c|\right)=O(n\mathrm{\Delta }).$$

  If $\mathrm{\Delta }\ll n$, then this is a significant improvement over the naive bound of $O(n^2)$ distinct pairs (or distinct output subsequences).

• $\mathrm{■}$

  Reduction to an uncolored problem. For each possible output subsequence $S$ of color $c$ with $p_i\in {𝒫}_c$ (resp., $p_j\in {𝒫}_c$) as the first (resp., last) point point on $S$, we construct an axis-aligned rectangle $R_c(i,j)$ with $p_i$ (resp., $p_j$) as the bottom-left (resp., top-right) corner. A weight $w(R_c(i,j))$ is associated with rectangle $R_c(i,j)$ which is equal to $\mathrm{𝖫𝖨𝖲}({𝒫}_c\cap R_c(i,j))$. See Figure 6. Let $ℛ$ be the collection of $O(n\mathrm{\Delta })$ such weighted rectangles. As a result, the problem of $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ is now reduced to the rectangle range-max problem, where given an axis-parallel rectangle $q$, among all the rectangles in $ℛ$ which lie completely inside $q$, the goal is to report the rectangle with the largest weight.

  It is crucial to note that the colored problem has been reduced to a problem on uncolored rectangles for which an efficient data structure exists: the rectangle range-max data structure can be constructed in $\tilde{O}(|ℛ|)=\tilde{O}(n\mathrm{\Delta })$ time and the $m$ range queries can be answered in $\tilde{O}(m)+O(k)$ time.

Define a parameter $\mathrm{\Delta }$ which will be set later. A color $c$ is classified as light if $|{𝒫}_c|\le \mathrm{\Delta }$, otherwise, it is classified as heavy. We will design different algorithms to handle light colors and heavy colors. The advantage with a light color, say $c$, is that we can precompute the $\mathrm{𝖫𝖨𝖲}$ for $O({|{𝒫}_c|}^2)$ 2D axis-parallel ranges and still be within the time budget. On the other hand, the advantage with heavy colors is that there can be only $O(n/\mathrm{\Delta })$ heavy colors.

Let ${𝒫}_{\mathrm{\ell }}\subseteq 𝒫$ be the set of points which belong to a light color. We will use the third technique to answer $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ on ${𝒫}_{\mathrm{\ell }}$ and queries $𝒬$. It follows that the running time is $\tilde{O}(m+n\mathrm{\Delta })+O(k)$ (see the full version of the paper for details).

Let ${𝒫}_h\subseteq 𝒫$ be the set of points which belong to a heavy color. In the full version of the paper we will prove that for an arbitrary value of $\tau$, the running time of the first technique will be $\tilde{O}(m\tau +n\tau )$. The first technique as described above only handles uncolored points. In the full version of the paper we will “generalize” the first technique to answer $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem as well. The running time of this generalized first technique on colored pointset ${𝒫}_h$ and queries $𝒬$ will be $\tilde{O}\left(\frac{m\tau n}{\mathrm{\Delta }}+\frac{n^2\tau }{\mathrm{\Delta }}\right)+O(k)$, where the number of heavy colors is $O(n/\mathrm{\Delta })$.

In the full version of the paper we will prove that for an arbitrary $\tau$, the running time of the second technique will be $\tilde{O}\left(\frac{mn}{\tau }+\frac{n^2}{\tau }\right)+O(k)$ for $\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ problem. In fact, we will generalize this algorithm to the large $\mathrm{𝖫𝖨𝖲}$ case of $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ with the same running time (ignoring polylogarithmic factors). The generalized algorithm will answer $\mathrm{𝐶𝑜𝑙𝑜𝑟𝑒𝑑}\text{-}\mathit{2}D\text{-}\mathrm{𝑅𝑎𝑛𝑔𝑒}\text{-}\mathrm{𝐿𝐼𝑆}$ on ${𝒫}_h$ and queries $𝒬$.

Combining all the three subroutines, the total running time will be:

We set the parameters $\tau \leftarrow n^{1/3}$ and $\mathrm{\Delta }\leftarrow n^{2/3}$ in the above expression to obtain a running time of $\tilde{O}(m{n}^{2/3}+n^{5/3})+O(k)$.