$a\in[0\mathinner{.\,.}|X|+|Y|)$. The sets $R$ and $R^{\prime}$ can be
constructed using the already available functions
$\mathsf{xi}(\pi,\cdot),\mathsf{xi}(\pi^{\prime},\cdot),\mathsf{yi}(\pi,\cdot),\mathsf{yi}(\pi^{\prime},\cdot)$
and sorted by scanning $[0\mathinner{.\,.}n+m]$ from left to right.

Overall, the second phase of the algorithm results in the (remaining) values
of $\sigma$ for arguments arguments in $R$. It is easy to see that the running
time of the entire algorithm is $O(n+m)$. ∎

####  3.2.7 Efficient Distance Oracle

In this section, we combine the insight from Sections 3.2.5 and 3.2.6 to
develop a divide-and-conquer algorithm constructing the seaweed matrix $P_{G}$
of a given slice alignment graph $G=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$.
This algorithm is optimized for the setting when $S$ is a sparse subset of
$\mathcal{G}^{n-1,m-1}$, and it generalizes [Tis13, Algorithm 8.2]. As a
corollary, we derive an efficient construction procedure for an oracle
providing random access to the distance matrix $D_{G}$.

######  Proposition 28.

Given a slice alignment graph $G=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$
(represented by $\pi$, $\pi^{\prime}$, and $S$), the permutation representing
$P_{G}$ can be constructed in $O(1+n+m+|S|\log^{2}|S|)$ time.

###### Proof.

We develop a recursive divide-and-conquer algorithm. The points in
$S\setminus\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime})$ do not
contribute any edge in $G$, so they are removed from $S$ in a preprocessing
step of the algorithm. Then, the algorithm computes $X=\\{x:(x,y)\in S\\}$ and
$Y=\\{y:(x,y)\in S\\}$. This can be implemented in $O(n+m+|S|)$ time by
iterating over the points in $S$, with $X\subseteq[0\mathinner{.\,.}n)$ and
$Y\subseteq[0\mathinner{.\,.}m)$ maintained as characteristic vectors.

If $X\neq[0\mathinner{.\,.}n)$ or $Y\neq[0\mathinner{.\,.}m)$, the algorithm
reduces the grid dimensions based on the combinatorial insight of Section
3.2.6. First, we construct the functions
$\mathsf{rk}_{X}:[0\mathinner{.\,.}n]\to[0\mathinner{.\,.}|X|]$ and
$\mathsf{rk}_{Y}:[0\mathinner{.\,.}m]\to[0\mathinner{.\,.}m]$ so that
$\mathsf{d}_{X,Y}(x,y)$ can be retrieved in $O(1)$ time for every
$(x,y)\in\mathcal{G}^{n,m}$. Next, we build
$\widetilde{\pi}:=\mathsf{d}_{X,Y}(\pi)$,
$\widetilde{\pi}^{\prime}:=\mathsf{d}_{X,Y}(\pi^{\prime})$, and
$\widetilde{S}:=\\{\mathsf{d}_{X,Y}(p):p\in S\\}$. By Lemma 24, this yields a
slice alignment graph
$\widetilde{G}=\mathsf{SAG}^{|X|,|Y|}(\widetilde{\pi},\widetilde{\pi}^{\prime},\widetilde{S})$,
which is processed recursively, with the algorithm of Lemma 27 applied to
transform the permutation representing $P_{\widetilde{G}}$ to the permutation
representing $P_{G}$.

It remains to consider the case when $X=[0\mathinner{.\,.}n)$ and
$Y=[0\mathinner{.\,.}m)$. In particular, if $|S|=0$, then $n=m=0$,
$D_{G}=\begin{bmatrix}0\end{bmatrix}$, and $P_{G}$ is the empty ($0\times 0$)
matrix (represented by the empty permutation). Similarly, if $|S|=1$, then we
must have $\pi=((0,1),(0,0),(1,0))$, $\pi^{\prime}=(0,1),(1,1),(1,1)$, and
$S=\\{(0,0)\\}$. Consequently,

$D_{G}=\begin{bmatrix}0&1&2\\\ 1&0&1\\\
2&1&0\end{bmatrix}\qquad\text{and}\qquad
P_{G}=\tfrac{1}{2}D_{G}^{\square}=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix},$

which is represented by the identity permutation on $\\{0,1\\}$.

Thus, we may henceforth assume $|S|\geq\max(n,m,2)$. In this case, the
algorithm decomposes $G$ into two smaller slice alignment graphs based on the
combinatorial insight of Section 3.2.5. First, we partition $S$ into $S_{L}$
and $S_{R}$ so that $|S_{L}|=\lceil\frac{1}{2}|S|\rceil$,
$|S_{R}|=\lfloor\frac{1}{2}|S|\rceil$, and points in $S_{L}$ are
lexicographically smaller than points in $S_{R}$ (note that both sets are non-
empty).

Let $(\mkern 1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu,\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu)$ be the
lexicographically smallest element of $S_{R}$. We define the following cut-
path $\pi^{-}:(0,m),\ldots,(\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu,m),\ldots,(\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu,\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu),(\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu+1,\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu),\ldots,(\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu+1,0),\ldots,(n,0)$.
Formally,

$\pi^{-}_{d}=\begin{cases}(d,m)&\text{if }d\in[0\mathinner{.\,.}\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu],\\\ (\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu,\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu+m-d)&\text{if
}d\in[\mkern 1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu\mathinner{.\,.}\mkern 1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu-\mkern 1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu+m],\\\
(\mkern 1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu+1,\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu+m-d)&\text{if
}d\in(\mkern 1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu-\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu+m\mathinner{.\,.}\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu+m],\\\ (d-m,0)&\text{if
}d\in[\mkern 1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu+m\mathinner{.\,.}n+m].\end{cases}$

This way, every point $p\in S\cap\mathcal{D}^{n,m}_{d}$ satisfies
$p\prec\pi^{-}_{d}$ if $p\in S_{L}$ and $\pi^{-}_{d}\preceq p$ if $p\in
S_{R}$.

Next, we define another cut-path $\pi^{\prime\prime}$ with

$\pi^{\prime\prime}_{d}=\begin{cases}\pi_{d}&\text{if
}\pi^{-}_{d}\preceq\pi_{d}\preceq\pi^{\prime}_{d},\\\ \pi^{-}_{d}&\text{if
}\pi_{d}\preceq\pi^{-}_{d}\preceq\pi^{\prime}_{d},\\\
\pi^{\prime}_{d}&\text{if
}\pi_{d}\preceq\pi^{\prime}_{d}\preceq\pi^{-}_{d}.\\\ \end{cases}$

This guarantees $\pi\preceq\pi^{\prime\prime}\preceq\pi^{\prime}$. Moreover,
since $S\subseteq\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime})$, we have
$S_{L}=S\cap\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime\prime})$ and
$S_{R}=S\cap\mathcal{G}^{n,m}[\pi^{\prime\prime}\mathinner{.\,.}\pi^{\prime})$.
This yields slice alignment graphs
$G_{L}:=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S_{L})$ and
$G_{R}:=\mathsf{SAG}^{n,m}(\pi^{\prime\prime},\pi^{\prime},S_{R})$. These
graphs are processed recursively and then Lemma 20 is used to derive the
permutation representing $P_{G}$ from the permutations representing
$P_{G_{L}}$ and $P_{G_{R}}$.

It remains to analyze the running time. For this, we interpret the grid size
reduction as a preprocessing step rather than a standalone recursive call. If
$|S|\leq 1$, then the algorithm takes $O(n+m+1)$ time. Otherwise, it takes
$O(n+m+|S|\log|S|)$ time and makes two recursive calls. The grid dimensions in
these calls do not exceed $|S|$ and the sets $S_{L}$ and $S_{R}$ in the calls
are of size at most $\lceil\frac{1}{2}|S|\rceil$. This yields an overall bound
of $O(1+n+m+|S|\log^{2}|S|)$ on the running time. ∎

######  Corollary 29.

For every slice alignment graph $G=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$,
there is a data structure of size $O(n+m)$ that, given any
$a,b\in[0\mathinner{.\,.}n+m]$, computes $D_{G}[a,b]$ in
$O(\log(n+m)/\log\log(n+m))$ time. Moreover, the data structure can be
constructed in $O((n+m)\sqrt{\log(n+m)}+|S|\log^{2}|S|)$ time given $\pi$,
$\pi^{\prime}$, and $S$.

###### Proof.

Note that $D_{G}[a,b]=2M_{G}[a,b]+a-b=2P^{\Sigma}_{G}[a,b]+a-b$ holds for
$a,b\in[0\mathinner{.\,.}n+m]$. Hence, it suffices to store the data structure
of 10 providing random access to $P_{G}^{\Sigma}$, which takes $O(n+m)$ space
and answers queries in $O(\log(n+m)/\log\log(n+m))$ time. The construction
time is $O((n+m)\sqrt{\log(n+m)})$ from the permutation representing $P_{G}$,
which can be built in $O(n+m+|S|\log^{2}|S|)$ time using Proposition 28. ∎

####  3.2.8 Applications to LIS

In this section, we provide a 3-step proof of Theorem 5. In Lemma 30, we use
Lemmas 12 and 17 to interpret the outcome of Corollary 29 in terms of the
values $\mathsf{LIS}(S^{\prime})$ for appropriate subsets $S^{\prime}\subseteq
S$. Here, the main technical challenge is to make sure that these values form
an anti-Monge matrix even though some entries in this matrix correspond to
degenerate queries. Corollary 31 generalizes Lemma 30 so that two arbitrary
antichains are supported instead of two cut-paths. We use 15 to extend
antichains to cut-paths, but then extra care is needed to obtain cut-paths
satisfying $\pi\preceq\pi^{\prime}$. Finally, we derive Theorem 5 by
interpreting a sequence $(a_{i})_{i=0}^{n-1}$ as a set
$S\subseteq\mathcal{G}^{n-1,n-1}$ and its non-increasing subsequences as
antichains in $\mathcal{G}^{n,n}$.

######  Lemma 30.

Let $G=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$ be a slice alignment graph with
$\pi=(x_{d},y_{d})_{d=0}^{n+m}$ and
$\pi^{\prime}=(x^{\prime}_{d},y^{\prime}_{d})_{d=0}^{n+m}$, and let $N>0$ be
an integer. There exists an anti-Monge matrix
$L\in\mathbb{R}^{(n+m+1)\times(n+m+1)}$ such that, for every
$i,j\in[0\mathinner{.\,.}n+m+1]$, we have

$\displaystyle L[i,j]$
$\displaystyle=\mathsf{LIS}(S\cap[x_{i}\mathinner{.\,.}x^{\prime}_{j})\times[y_{i}\mathinner{.\,.}y^{\prime}_{j}))$
$\displaystyle\text{if }x_{i}\leq x^{\prime}_{j}\text{ and }y_{i}\leq
y^{\prime}_{j},$ $\displaystyle L[i,j]$ $\displaystyle\leq-N$ otherwise.

Moreover, after $O((n+m)\sqrt{\log(n+m)}+|S|\log^{2}|S|)$-time preprocessing,
any entry of $L$ can be computed in $O(\log(n+m)/\log\log(n+m))$ time.

###### Proof.

Let us define another slice alignment graph
$G^{\prime}=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},\emptyset)$. By Lemma 19, both
$D_{G}$ and $D_{G^{\prime}}$ are Monge matrices. Moreover, define a matrix
$A\in\mathbb{R}^{(n+m+1)\times(n+m+1)}$ so that
$A[i,j]=x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i}$ and note that $A^{\square}$
is zero matrix, i.e., $A$ is both a Monge and an anti-Monge matrix.

We define the matrix $L$ as the following linear combination of $D_{G}$,
$D_{G^{\prime}}$, and $A$:

$L=\tfrac{1}{2}(N\cdot A-D_{G}-(N-1)\cdot D_{G^{\prime}}).$

It is an anti-Monge matrix because $D_{G}$ and $D_{G^{\prime}}$ are Monge
matrices whereas $A$ is an anti-Monge matrix (since $A^{\square}$ is a zero
matrix).

It remains to check whether $L$ satisfies the required conditions.

  * •

If $x_{i}\leq x^{\prime}_{j}$ and $y_{i}\leq y^{\prime}_{j}$, then Lemmas 12
and 17 yield
$D_{G}[i,j]=x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i}-2\mathsf{LIS}(S\cap[x_{i}\mathinner{.\,.}x^{\prime}_{j})\times[y_{i}\mathinner{.\,.}y^{\prime}_{j}))$
and $D_{G^{\prime}}[i,j]=x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i}$. Hence,
$2L[i,j]=N(x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i})-(x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i}-2\mathsf{LIS}(S\cap[x_{i}\mathinner{.\,.}x^{\prime}_{j})\times[y_{i}\mathinner{.\,.}y^{\prime}_{j})))-(N-1)(x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i})=2\mathsf{LIS}(S\cap[x_{i}\mathinner{.\,.}x^{\prime}_{j})\times[y_{i}\mathinner{.\,.}y^{\prime}_{j}))$
holds as claimed.

  * •

If $x_{i}\leq x^{\prime}_{j}$ and $y_{i}>y^{\prime}_{j}$, then Lemmas 12 and
17 yield
$D_{G}[i,j]=D_{G^{\prime}}[i,j]=x^{\prime}_{j}-x_{i}+y_{i}-y^{\prime}_{j}$.
Hence,
$2L[i,j]=N(x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i})-N(x^{\prime}_{j}-x_{i}+y_{i}-y^{\prime}_{j})=2N(y^{\prime}_{j}-y_{i})\leq-2N$
holds as claimed.

  * •

If $x_{i}>x^{\prime}_{j}$ and $y_{i}\leq y^{\prime}_{j}$, then Lemmas 12 and
17 yield
$D_{G}[i,j]=D_{G^{\prime}}[i,j]=x_{i}-x^{\prime}_{j}+y^{\prime}_{j}-y_{j}$.
Hence,
$2L[i,j]=N(x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i})-N(x_{i}-x^{\prime}_{j}+y^{\prime}_{j}-y_{j})=2N(x^{\prime}_{j}-x_{i})\leq-2N$
holds as claimed.

  * •

If $x_{i}>x^{\prime}_{j}$ and $y_{i}>y^{\prime}_{j}$, then $D_{G}[i,j]\geq 0$
and Lemmas 12 and 17 yields
$D_{G^{\prime}}[i,j]=x_{i}-x^{\prime}_{j}+y_{i}-y^{\prime}_{j}$. Hence,
$2L[i,j]\leq
N(x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i})-(N-1)(x_{i}-x^{\prime}_{i}+y_{i}-y^{\prime}_{j})=(2N-1)(x^{\prime}_{j}-x_{i}+y^{\prime}_{j}-y_{i})\leq-(4N-2)\leq-2N$
holds as claimed.∎

Our next goal is to generalize Lemma 30 from cut-paths
$\pi\preceq\pi^{\prime}$ to arbitrary antichains.

######  Corollary 31.

Let $(x_{i},y_{i})_{i=0}^{k-1}$ and
$(x^{\prime}_{j},y^{\prime}_{j})_{j=0}^{\ell-1}$ be antichains in
$\mathcal{G}^{n,m}$, let $S\subseteq\mathcal{G}^{n-1,m-1}$, and let $N>0$ be a
positive integer. There exists an anti-Monge matrix
$M\in\mathbb{R}^{(n+m+1)\times(n+m+1)}$ such that, for every
$i\in[0\mathinner{.\,.}k)$ and $j\in[0\mathinner{.\,.}\ell)$, we have

$\displaystyle M[i,j]$
$\displaystyle=\mathsf{LIS}(S\cap[x_{i}\mathinner{.\,.}x^{\prime}_{j})\times[y_{i}\mathinner{.\,.}y^{\prime}_{j}))$
$\displaystyle\text{if }x_{i}\leq x^{\prime}_{j}\text{ and }y_{i}\leq
y^{\prime}_{j},$ $\displaystyle M[i,j]$ $\displaystyle\leq-N$ otherwise.

Moreover, after $O((n+m)\sqrt{\log(n+m)}+|S|\log^{2}|S|)$-time preprocessing,
any entry of $M$ can be computed in $O(\log(n+m)/\log\log(n+m))$ time.

###### Proof.

Let us extend $(x_{i},y_{i})_{i=0}^{k-1}$ to a cut-path $\pi$ and
$(x^{\prime}_{j},y^{\prime}_{j})_{j=0}^{\ell-1}$ to a cut-path $\pi^{\prime}$
using 15. Next, define a cut-paths $\widetilde{\pi}$ and
$\widetilde{\pi}^{\prime}$ so that, for every $d\in[0\mathinner{.\,.}n+m]$:

$\displaystyle\widetilde{\pi}_{d}=\pi_{d}\text{ and
}\widetilde{\pi}^{\prime}_{d}=\pi^{\prime}_{d}$ $\displaystyle\text{ if
}\pi_{d}\preceq\pi^{\prime}_{d},$
$\displaystyle\widetilde{\pi}_{d}=\pi^{\prime}_{d}\text{ and
}\widetilde{\pi}^{\prime}_{d}=\pi_{d}$ $\displaystyle\text{ if
}\pi^{\prime}_{d}\preceq\pi_{d}.$

Note that this guarantees $\widetilde{\pi}\preceq\widetilde{\pi}^{\prime}$.
Moreover, define a graph
$G=\mathsf{SAG}^{n,m}(\widetilde{\pi},\widetilde{\pi}^{\prime},S)$ and
consider the matrix $L$ of Lemma 30. Let $\widetilde{M}$ be a submatrix of $L$
defined so that
$\widetilde{M}[i,j]=L[x_{i}-y_{i}+m,x^{\prime}_{j}-y^{\prime}_{j}+m]$ for
$i\in[0\mathinner{.\,.}k)$ and $j\in[0\mathinner{.\,.}\ell)$. Furthermore, let
$M$ be obtained from $\widetilde{M}$ by subtracting $N+|S|$ from any row $i$
such that $\widetilde{\pi}_{x_{i}-y_{i}+m}\neq(x_{i},y_{i})$ and subtracting
$N+|S|$ from any column $j$ such that
$\widetilde{\pi}^{\prime}_{x^{\prime}_{j}-y^{\prime}_{j}+m}\neq(x^{\prime}_{j},y^{\prime}_{j})$.

The sequences $(x_{i}-y_{i}+m)_{i=0}^{k-1}$ and
$(x^{\prime}_{j}-y^{\prime}_{j}+m)_{j=0}^{\ell-1}$ are strictly increasing, so
$\widetilde{M}$ is an anti-Monge matrix. Moreover,
$M^{\square}=\widetilde{M}^{\square}$, so $M$ is also an anti-Monge matrix.
Furthermore, the entries of $L$ can be computed in
$O(\log(n+m)/\log\log(n+m))$ time after
$O((n+m)\sqrt{\log(n+m)}+|S|\log^{2}|S|)$-time preprocessing, so the same is
true about the entries of $M$.

It remains to prove that each value $M[i,j]$ satisfies the desired properties.
Let $d=x_{i}-y_{i}+m$ and $d^{\prime}=x^{\prime}_{j}-y^{\prime}_{j}+m$. First,
suppose that $\widetilde{\pi}_{d}=(x_{i},y_{i})$ and
$\widetilde{\pi}^{\prime}_{d}=(x^{\prime}_{j},y^{\prime}_{j})$, in which case
$M[i,j]=\widetilde{M}[i,j]=L[d,d^{\prime}]$. By Lemma 30, the we have
$L[d,d^{\prime}]=\mathsf{LIS}(S\cap[x_{i}\mathinner{.\,.}x^{\prime}_{j})\times[y_{i}\mathinner{.\,.}y^{\prime}_{j}))$
if $x_{i}\leq x^{\prime}_{j}$ and $y_{i}\leq y^{\prime}_{j}$, and
$L[d,d^{\prime}]=-N$ otherwise. Hence, the $M[i,j]$ satisfies the claim in
this case.

Next, suppose that $\widetilde{\pi}_{d}\neq(x_{i},y_{i})$. In this case, we
have $(x_{i},y_{i})=\pi_{d}\succ\pi^{\prime}_{d}$. Consequently, if $x_{i}\leq
x^{\prime}_{j}$ and $y_{i}\leq y^{\prime}_{j}$, then
$\pi^{\prime}_{d^{\prime}}=(x^{\prime}_{j},y^{\prime}_{j})\succ\pi^{\prime}_{d}$,
which contradicts $\pi^{\prime}$ being an antichain. Thus, it suffices to
prove that $M[i,j]\leq-N$. However, we have
$M[i,j]\leq\widetilde{M}[i,j]-N-|S|=L[d,d^{\prime}]-N-|S|\leq|S|-N-|S|\leq-N$,
as claimed.

Symmetrically, if
$\widetilde{\pi}^{\prime}_{d^{\prime}}\neq(x^{\prime}_{j},y^{\prime}_{j})$,
then
$(x^{\prime}_{j},y^{\prime}_{j})=\pi^{\prime}_{d^{\prime}}\prec\pi_{d^{\prime}}$.
If $x_{i}\leq x^{\prime}_{j}$ and $y_{i}\leq y^{\prime}_{j}$, then
$\pi_{d}=(x_{i},y_{i})\prec\pi_{d^{\prime}}$, which contradicts $\pi$ being an
antichain. At the same time, $M[i,j]\leq\widetilde{M}[i,j]-N-|S|\leq
L[d,d^{\prime}]-N-|S|$ holds as claimed. ∎

Finally, we derive Theorem 5, whose statement is repeated below for reader’s
convenience. See 5

###### Proof.

Without loss of generality, we may assume that the values $a_{i}$ belong to
$[0\mathinner{.\,.}n)$. If this is not the case, we can construct a set
$A=\\{a_{i}:i\in[0\mathinner{.\,.}n)\\}$ and replace each value $a_{i}$ with
its rank $\mathsf{rk}_{A}(a_{i})$. This transformation preserves the relative
order between any two values $a_{i}$ and $a_{j}$, so it preserves monotonicity
of subsequences.

We construct a set
$S=\\{(i,a_{i}):i\in[0\mathinner{.\,.}n)\\}\subseteq\mathcal{G}^{n-1,n-1}$,
observing that increasing subsequences of $(a_{i})_{i=0}^{n-1}$ correspond to
chains in $S$. We also define two sequences of points in $\mathcal{G}^{n,n}$:
$(x_{i},y_{i})_{i=0}^{k-1}=(p_{i}+1,a_{p_{i}}+1)_{i=0}^{k-1}$ and
$(x^{\prime}_{j},y^{\prime}_{j})_{j=0}^{\ell-1}=(q_{j},a_{q_{j}})_{j=0}^{\ell-1}$.
Both are antichains because $(a_{p_{i}})_{i=0}^{k-1}$ and
$(a_{q_{j}})_{j=0}^{\ell-1}$ are non-increasing.

Now, let $M^{\prime}$ be the matrix of Corollary 31 constructed for
$N^{\prime}=N+2$, and let $M$ be obtained from $M^{\prime}$ by setting
$M[i,j]=M^{\prime}[i,j]+2$ for each $i\in[0\mathinner{.\,.}k)$ and
$j\in[0\mathinner{.\,.}\ell)$. Since $M^{\prime}$ is an anti-Monge matrix, so
is $M$. Furthermore, due to $|S|=n$, any entry of $M$ can be computed in
$O(\log n/\log\log n)$ time after $O(n\log^{2}n)$-time preprocessing.

Thus, it remains to prove that each value of $M[i,j]$ satisfies the desired
properties. If $p_{i}<q_{j}$ and $a_{p_{i}}<a_{q_{j}}$, then
$x_{i}=p_{i}+1\leq q_{j}=x^{\prime}_{j}$ and $y_{i}=a_{p_{i}}+1\leq
a_{q_{j}}=y^{\prime}_{j}$, so
$M[i,j]=2+M^{\prime}[i,j]=2+\mathsf{LIS}(S\cap[p_{i}+1\mathinner{.\,.}q_{j})\times(a_{p_{i}}+1\mathinner{.\,.}a_{q_{j}}))$.
The latter value is equal to the length of the longest chain starting from
$(p_{i},a_{p_{i}})$ to $(q_{j},a_{q_{j}})$, i.e.., the longest increasing
subsequence from $a_{p_{i}}$ to $a_{q_{j}}$. On the other hand, if $p_{i}\geq
q_{j}$, then $x_{i}=p_{i}+1>q_{j}=x^{\prime}_{j}$, and if $a_{p_{i}}\geq
a_{q_{j}}$, then $y_{i}=a_{p_{i}}+1>a_{q_{j}}=y^{\prime}_{j}$. In either case,
$M[i,j]=2+M^{\prime}[i,j]\leq 2-N^{\prime}=-N$ holds as claimed. ∎

##  4 Improved Approximation Algorithms for LIS

In this section, we present applications of extended grid packing. We begin by
stating our key lemma for extended grid packing in Section 4.1. We then bring
a use case of the extended grid packing technique for a non-dynamic problem in
Section 4.2. This makes it clear how the new technique can be used to
approximate LIS. We then bring a more detailed discussion as to why extended
grid packing leads to a dynamic algorithm for LIS. While at a high-level, both
our dynamic and non-dynamic algorithms make use of extended grid packing in a
similar way, the dynamic algorithm requires additional considerations to
ensure the update time remains bounded in the worst case.

###  4.1 Extended Grid Packing

As explained earlier, grid packing is a tool for approximating LIS. For
completeness, we first state the definitions. In this problem, we have a table
of size $m\times m$. Our goal is to introduce a number of segments on the
table. Each segment either covers a consecutive set of cells in a row or in a
column. A segment $A$ precedes a segment $B$ if every cell of $A$ is strictly
higher than every cell of $B$ and also every cell of $A$ is strictly to the
right of every cell of $B$. Two segments are non-conflicting, if one of them
precedes the other one. Otherwise, we call them conflicting. The segments we
introduce can overlap and there is no restriction on the number of segments or
the length of each segment. However, we would like to minimize the maximum
number of segments that cover each cell.

Figure 7: Segments are shown on the grid. The pair (black, orange) is
conflicting since the yellow cell (covered by the black segment) is on the
same row as the blue cell (covered by the orange segment). The following pairs
are non-conflicting: (green, black), (green, orange), (green, blue), (red,
orange), (red, blue), (black, blue).

After we choose the segments, an adversary puts a non-negative number on each
cell of the table. The score of a subset of cells of the table would be the
sum of their values and the overall score of the table is the maximum score of
a path of length $2m-1$ from the bottom-left corner to the top-right corner.
In such a path, we always either move up or to the right.

The score of a segment is the sum of the numbers on the cells it covers. We
obtain the maximum sum of the scores of a non-conflicting set of segments. The
score of the table is an upper bound on the score of any set of non-
conflicting segments. We would like to choose segments so that the ratio of
the score of the table and our score is bounded by a constant, no matter how
the adversary puts the numbers on the table. More precisely, we call a
solution $(\alpha,\beta)$-approximate, if at most $\alpha$ segments cover each
cell and it guarantees a $1/\beta$ fraction of the score of the table for us
for any assignment of numbers to the table cells.

$2$$0$$2$$3$$1$$1$$5$$0$$1$$0$$3$$0$$2$$1$$0$$1$ Figure 8: After we introduce
the segments (left figure), the adversary puts the numbers on the table
(middle figure). In this case, the score of the table is equal to $12$ (via
the path depicted on the right figure), and our score is equal to $9$ obtained
from two non-conflicting segments green and blue.

Mitzenmacher and Seddighin [MS20] prove the following theorem: For any
$m\times m$ table and any $0<\kappa<1$, there exists a grid packing solution
with guarantee $(O_{\kappa}(m^{\kappa}\log m),O(1/\kappa))$. That is, each
cell is covered by at most $O_{\kappa}(m^{\kappa}\log m)$ segments and the
ratio of the table’s score over our score is bounded by $O(1/\kappa)$ in the
worst case.

The general framework of grid packing remains the same for our extension: The
problem can be thought of as a game played on an $m\times m$ table against an
adversary and the goal is to introduce some multisegments (a generalization of
segments explained below) such that after the adversary puts her numbers on
the table cells, the score we obtain is comparable to table’s score. However,
extended grid packing differs with grid packing in two ways: First, we
introduce a new notion that we call a multisegment and we allow the use of
multisegments instead of segments. Second, we do not enforce any bound on the
number of multisegments that cover each cell. That is, we only have one
objective which is maximizing the ratio of our score over the score of the
table. Without the bound, utilizing extended grid packing for LIS becomes
harder as previous solutions require a cap on the maximum number of segments
covering each cell. However, we present in Section 4.2 a more clever
application of extended grid packing that does not depend on this bound.

Before we introduce multisegments, let us give an example to illustrate why
segments fall short of our purpose which is obtaining a $(1-\epsilon)$
fraction of the table’s score. For an $m\times m$ table, there are
$m\binom{m}{2}+m^{2}$ distinct horizontal segments and $m\binom{m}{2}+m^{2}$
distinct vertical segments that amount to $2m\binom{m}{2}+m^{2}$ segments in
total (there are $m^{2}$ single cell segments that can be regarded as both
vertical and horizontal). Figure 9 gives an example that proves we cannot
obtain a score more than $2/3$ of the score of the table. In this example,
even if we introduce all possible $2m\binom{m}{2}+m^{2}$ segments, from every
three consecutive cells with value $1$ no more than two can be covered by non-
conflicting segments. Thus, we cannot obtain more than $2/3$ of the score of
the table even if there is no restriction on the maximum number of segments
covering each cell.

$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$
Figure 9: Only the cells of one path from the bottom-left to the top-right
have value 1 and the value of the rest of the cells is 0. We can obtain a
score of 10 by using the green segments but we miss 5 cells with value 1
(colored in orange). Also, other non-conflicting combinations of segments miss
at least 5 cells with value 1.

The example of Figure 9 highlights the fact that even if all possible segments
can be used in a solution, there is no hope to obtain a $1-\epsilon$ fraction
of the score of the table. This is the main motivation behind the definition
of multisegments. As we show later, multisegments enable us to obtain a score
arbitrarily close to the score of the table.

For a horizontal/vertical segment, we define its first cell as its
leftmost/bottommost cell and its last cell as the rightmost/topmost cell of
the segment. A $\Delta$-multisegment is defined as a combination of $\Delta$
segments $s_{1},s_{2},\ldots,s_{\Delta}$ where for each $1\leq i\leq\Delta-1$,
the last cell of segment $s_{i}$ is the same as the first cell of segment
$s_{i+1}$. By definition, the notion of $1$-multisegment collides with that of
segment. We say a multisegment covers a cell, if any of its segments covers
that cell. Moreover, two multisegments $S_{1}$ and $S_{2}$ are non-
conflicting, if for each segment $x$ of $S_{1}$ and each segment $y$ of
$S_{2}$, $x$ and $y$ are non-conflicting. To avoid confusion, we use uppercase
letters for multisegments and lowercase letters for segments. Based on this
definition, for any $1\leq i<\Delta$, an $i$-multisegment is also a
$\Delta$-multisegment (we may add $\Delta-i$ single cell segments to an
$i$-multisegment to make it compatible with the definition of
$\Delta$-multisegment without any change in its shape).

Figure 10: All polylines except for the green one are valid multisegments.
Yellow and gray multisegments are non-conflicting, while the rest of the
multisegment pairs are conflicting.

We define an extended version of the grid packing problem as a game between us
and an adversary. Similar to grid packing, we first introduce a number of
multisegments and then the adversary puts nonnegative numbers on the cells of
the table. Then, table’s score is formulated as the largest sum the adversary
can collect from the values of the cells by moving from the bottom-left corner
to the top-right corner of the table. Our score is the largest sum we can
collect by non-conflicting multisegments where the value of a multisegment is
equal to the total sum of the numbers of the cells it covers.

As we show in Lemma 32, if for a $\Delta$, we consider all possible
$\Delta$-multisegments in our solution, our score is always at least a
$\frac{\Delta-1}{\Delta}$ fraction of the table’s score. Notice that by
introducing all such multisegments, a cell may be covered by many
multisegments.

######  Lemma 32.

For a fixed $1\leq\Delta$, if we introduce all $\Delta$-multisegments in the
extended grid packing problem, our score will be least a
$\frac{\Delta-1}{\Delta}$ fraction of the table’s score regardless of the
values of the table cells.

###### Proof.

Let us fix the optimal path of length $2m-1$ from the bottom-left cell of the
table to the top-right cell which gives the highest score to the table. For
the sake of this proof, we give an ordering to the cells of this path. More
precisely, let $c_{1},c_{2},\ldots,c_{2m-1}$ be the sequence of these cells
where $c_{1}$ is the bottom-left corners and $c_{2m-1}$ is the top-right
corner and as we increase $i$, the distance of $c_{i}$ from $c_{1}$ increases.
We call a cell $c_{i}$ critical, if $1<i<2m-1$ and cells
$\\{c_{i-1},c_{i},c_{i+1}\\}$ cannot be covered by a single segment (i.e.,
they neither lie on the same row nor lie on the same column). In addition to
this, we consider both $c_{1}$ and $c_{2m-1}$ to be critical cells. The proof
is based on the following observations:

$\star$$\star$$\star$$\star$$\star$$\star$$\star$$\star$$\star$$\star$$\star$$\star$$\star$$\star$$\star$
Figure 11: An example of the optimal path is shown by starred cells. In this
example, all the critical cells are colored in blue.

  * •

For some $1\leq i\leq j\leq 2m-1$ all cells
$c_{i},c_{i+1},\ldots,c_{j-1},c_{j}$ can be covered by a single
$\Delta$-multisegment if no more than $\Delta-1$ cells in this set are
critical.

  * •

If cell $c_{i}$ is critical, then all cells $c_{i+1},c_{i+2},\ldots,c_{2m-1}$
are higher and to the right of all cells $c_{1},c_{2},\ldots,c_{i-1}$.

To complete the proof, we index the critical cells by their ordering. In other
words, let $r_{1},r_{2},\ldots,r_{k}$ be the critical cells of the table in
the order they are listed in the sequence $c_{1},\ldots,c_{2m-1}$ (here $k$ is
the number of critical cells). It follows from the above observations that
there are some non-conflicting $\Delta$-multisegements that cover all cells of
the path except for $r_{1},r_{\Delta+1},r_{2\Delta+1},r_{3\Delta+1},\ldots$.
More generally, for each $1\leq j\leq\Delta$, all cells of the optimal path
except for $r_{j},r_{\Delta+j},r_{2\Delta+j},r_{3\Delta+j},\ldots$ can be
covered by non-conflicting $\Delta$-multisegments. Since for at least one $j$,
such cells contribute to no more than a $1/\Delta$ fraction of the score of
the table, we can obtain at least a $\frac{\Delta-1}{\Delta}$ fraction of the
table’s score. ∎

Lemma 32 alone does not suffice to improve the dynamic algorithm of
Mitzenmacher and Seddighin [MS20] for LIS since their algorithm relies on a
bound on the number of segments that cover each cell. We remedy this issue by
presenting an alternative algorithm that does not require this bound. We
explain the new algorithm in details in Section 4.3.

###  4.2 A Data Structure for LIS

Previous work [MS20, MS21] illustrate natural connections between LIS and grid
packing. Generally, we represent the input sequence by points on the plane in
a way that a point with coordinates $(x,y)$ indicates that the $x$’s element
of the sequence has value $y$. Thus, instead of a sequence of length $n$, we
have a plane with $n$ points. This enables us to construct a grid, where the
rows and the columns evenly divide the points. Assuming the number the
adversary puts on each cell is the contribution of the points inside that cell
to the LIS of the sequence (which may be different from the LIS of the points
included in that cell), the score of the table (which we try to be competitive
to in extended grid packing) is always equal to the size of the optimal
solution. Moreover, the notion of non-conflicting segments/multisegments gives
us a way to construct a global solution by combining partial solutions. In
other words, if we associate a partial solution to each segment/multisegment
that only incorporates the points covered by those segments/multisegments,
then for a set of non-conflicting segments/multisegments, a combination of
partial solutions forms a valid increasing subsequence.

$\langle
7,2,4,1,9,6,3,5,8\rangle$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$
Figure 12: An array $\langle 7,2,4,1,9,6,3,5,8\rangle$ is mapped to the 2D
plane. $\langle
7,\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}2\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}4\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},1,9,\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}6\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},3,5,\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}8\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\rangle$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$1$$0$$0$$0$$0$$0$$1$$1$$1$
Figure 13: An array $\langle 7,2,4,1,9,6,3,5,8\rangle$ is mapped to the 2D
plane. An LIS is shown by green points. The plane is divided into a $3\times
3$ grid. The number on each cell is the equal to the contribution of that cell
to the LIS. The score of the grid is equal to the LIS of the array. The score
of the grid is made by the path colored in green.

We refer the reader to previous work [MS20, MS21] for discussions on how to
use grid packing for approximating LIS. Roughly speaking, after making a grid,
they construct a partial solution for each segment that keeps an approximation
to the LIS of the points covered by that segment. Thus, every time a change is
made, their algorithm has to update the solution for all segments that cover
the modified point. Therefore, previous techniques require a bound on the
number of segments that cover each cell of the grid. In order to obtain a
score arbitrarily close to the score of the table, we need to include a lot of
multisegments in our solution for extended grid packing, many of which cover
the same cells of the table. This makes it impossible for previous
applications to use the new construction. In this work, we introduce a new
application that does not require the bound. To illustrate the new technique,
we utilize extended grid packing to approximate the size of LIS in a non-
dynamic setting. We later bring a more involved description of the dynamic
algorithm.

Assume that we are given $n$ points on the plane with distinct coordinates. We
would like to make a preprocess on the points such that after that we can
(approximately) answer the following queries in polylogarithmic time: Given a
rectangle parallel to the axis lines, what is the LIS of the points included
in the rectangle? Recall that the LIS of a set of points is equal to the size
of the longest list of the points where the $x$ and $y$ coordinates increase
as the index of the elements increase in the list. To avoid confusion, we
assume that the $x$ and $y$ coordinates of the borders of the rectangles are
different from the coordinates of the points. We refer to this problem as
query-LIS.

Figure 14: The LIS of the points inside the red rectangle is equal to $2$.
This value for the points inside the green rectangle is equal to $3$ and for
the blue rectangle the LIS is equal to $4$.

There is a straightforward solution for query-LIS with preprocessing time
$O(n^{5}\log n)$ and query time $O(\log n)$. We first sort the $x$ and $y$
coordinates separately, and for every interval of the $x$ coordinates and $y$
coordinates we compute the LIS of the points within those intervals in time
$O(n\log n)$. Since there are $O(n^{2})$ intervals for $x$ coordinates and
$O(n^{2})$ intervals for $y$ coordinates, in total we compute the LIS of
$O(n^{4})$ subsets of the points and thus the overall runtime is $O(n^{5}\log
n)$. After this, whenever we are given a rectangle, we find the $x$ and $y$
intervals of the points covered by the rectangle and report the solution in
time $O(\log n)$. This algorithm is very inefficient and can be easily
improved in terms of preprocessing time, but for the sake of simplicity we do
not discuss those improvements here.

Instead, we explain an application of extended grid packing that improves the
preprocessing time of query-LIS down to $\widetilde{O}(n^{5/2})$ while keeping
its query time polylogarithmic. This comes at the expense of losing a factor
$1-\epsilon$ in the approximation. To this end, we define
$\epsilon^{\prime}=\epsilon/2$ and $\Delta=\lceil 1/\epsilon^{\prime}\rceil$.
Let $m=n^{5/8}$ be the table size in the extended grid packing problem and we
construct the table in a way that the rows and columns evenly divide the
points (in case the number of points is not divisible by $m$, we allow a
difference of $+1/-1$ in the number of points covered by each row and column).
After constructing the table, we define $2m$ subproblems each concerning the
points that fall within a row or a column. That is, in each subproblem, we
seek to solve query-LIS for a subset of points that lie either in a row or in
a column of the table. Thus, the size of each subproblem is $O(n^{3/8})$. We
use the naive solution with preprocessing time of $O(n^{5}\log n)$ for each
subproblem. This amounts to a total preprocessing time of

$O(2m(n/m)^{5}\log n)=O(n^{5}\log n/m^{4})=O(n^{5}\log
n/(n^{5/8})^{4})=O(n^{5/2}\log n).$

Figure 15: The red snake-lines show the grid and yellow and blue boxes present
the points included in each of the subproblems.

Before answering the queries, we run another algorithm to preprocess an
approximation to the LIS of some subsets of the points. More precisely, for
every interval of rows and every interval of columns of the table, we
preprocess the LIS of all the points that fall within the corresponding
rectangle and store the computed values. In other words, for
$(\binom{m}{2}+m)^{2}$ rectangles that can be formed by the rows and columns
of the table, we approximate their LIS. In our algorithm, every time we fix
the bottom-left corner of the rectangle, and for all possible top-right
corners, we dynamically approximate the solution. Thus, in what follows, we
fix a cell $c$ of the table and explain how we can approximate the value of
LIS for all rectangles whose bottom-left corner is $c$ in time
$\widetilde{O}_{\epsilon}(m^{2})$.

Our algorithm is based on a dynamic program. For each cell $c^{\prime}$ which
is not to the left of $c$ and is not below $c$, we define $f(c^{\prime})$ as
the LIS of the points inside the rectangle formed by $c$ and $c^{\prime}$ as
opposite corners and define $g(c^{\prime})$ that keeps an approximation of
$f(c^{\prime})$. We compute $g$ iteratively. Therefore, we start with
$c^{\prime}=c$ and move $c^{\prime}$ to the right step by step. When we reach
the end of the row, we start with the cell on top of $c$ and move it to the
right until we reach the end of the row and then we start with two cell above
$c$. We continue this procedure until we find a solution for the top-right
corner as the last rectangle.

Result:

1 construct an $m\times m$ grid whose rows and columns evenly divide the
points;

2 Initialize the subproblems;

3 for  _$x_{1}\leftarrow 1$ to $m$_ do

4 for  _$y_{1}\leftarrow 1$ to $m$_ do

5 $c\leftarrow$ cell $(x_{1},y_{1})$;

6 for  _$x_{2}\leftarrow x_{1}$ to $m$_ do

7 for  _$y_{2}\leftarrow y_{1}$ to $m$_ do

8 $c^{\prime}\leftarrow$ cell $(x_{2},y_{2})$;

9 if  _$x_{1}=y_{1}$ or $x_{2}=y_{2}$_ then

10 $g(c^{\prime})\leftarrow$LIS of the rectangle $(x_{1},y_{1},x_{2},y_{2})$;

11

12 end if

13 else

14
$g(c^{\prime})\leftarrow\max\\{g(\text{cell}(x_{2}-1,y_{2})),g(\text{cell}(x_{2},y_{2}-1))\\}$;

15 for  _$c^{\prime\prime}\in X$_ do

16 for  _$S\in Y(c^{\prime\prime})$_ do

17
$g(c^{\prime})\leftarrow\max\\{g(c^{\prime}),g(c^{\prime\prime})+\textsf{LIS}(S)\\}$;

18

19 end for

20

21 end for

22

23 end if

24

25 end for

26

27 end for

28

29 end for

30

31 end for

Algorithm 1 Inefficient preprocessing

In the DP, we use extended grid packing to estimate the LIS for each
rectangle. The base cases are when $c^{\prime}$ and $c$ are either within the
same row or within the same column in which case we can query the solution in
time $O(\log n)$ in one of the subproblems. Otherwise we estimate the value of
$f(c^{\prime})$ based on an analysis that is inspired by extended grid
packing. Suppose the extended grid packing is defined on our $m\times m$ table
and in our solution for extended grid packing, we introduce all possible
$\Delta$-multisegments. Moreover, assume that the numbers that the adversary
puts on the table cells are the contributions of the corresponding cells to
the LIS of the elements in the rectangle between $c$ and $c^{\prime}$. By
Lemma 32, there is a set of non-conflicting $\Delta$-multisegments that gives
us a score of at least $\frac{\Delta-1}{\Delta}f(c^{\prime})$. Moreover, the
LIS of the points covered by any multisegment is certainly an upper bound on
the value of that multisegment. Let $X$ be the set of all cells in the
rectangle between $c$ and $c^{\prime}$ except for $c^{\prime}$ and for any
cell $c^{\prime\prime}$, let $Y(c^{\prime\prime})$ be the set of all
$\Delta$-multisegments that start from the cell to the top and right of
$c^{\prime\prime}$ and end at cell $c^{\prime}$. Moreover, for a multisegment
$S$, we define $\textsf{LIS}(S)$ as the LIS of the points covered by $S$. For
now, we introduce the following recursive formula for approximating
$g(c^{\prime})$.

$g(c^{\prime}):=\max_{c^{\prime\prime}\in
X}\big{[}g(c^{\prime\prime})+\max_{S\in
Y(c^{\prime\prime})}\textsf{LIS}(S)\big{]}$

$c$$c^{\prime}$$c^{\prime\prime}$$S$$f(c^{\prime})\ \geq\ f(c^{\prime\prime})\
+\textsf{LIS}(S)$ Figure 16: The update process is explained in this figure

It follows from Lemma 32 that if we formulate $g(c^{\prime})$ as above,
$\frac{\Delta-1}{\Delta}f(c^{\prime})\leq g(c^{\prime})\leq f(c^{\prime})$
always holds. This gives us a formulation to recursively compute the value of
$g$ for all cells. However, there are two issues to be resolved: (i) there are
many possible cells $c^{\prime\prime}$ and multisegments $S$ that our
algorithm needs to loop over and thus the runtime of the algorithm is not as
desired. (ii) For a multisegment $S$, we do not have the value (or even an
estimate) of $\textsf{LIS}(S)$. We show in the following that both issues can
be resolved.

We begin by considering the simpler case of $\Delta=1$. Since in this case we
are only concerned with segments, for each segment $s$ we can compute
$\textsf{LIS}(s)$ by querying one of the subproblems (Recall that $s$ either
completely fits in a row or in a column of the table). Thus, for each segment
$s$, $\textsf{LIS}(s)$ is available in time $O(\log n)$. However, we still
need to resolve the first issue since there may be up to $O(m)$ different
segments that end at $c^{\prime}$. The idea is to reduce the number of
possible segments down to $O(\log n/\epsilon^{\prime})$ by losing a factor of
at most $1-\epsilon^{\prime}$ in the approximation. The base cases are trivial
as discussed previously, so for a cell $c^{\prime}$ we begin by initializing
$g(c^{\prime})$ as the maximum value for its left and bottom cells. This
ensures that our approximations are always monotone as should be. At a high-
level, for every value $v\in\mathbb{D}=\\{1,\lceil
1-\epsilon^{\prime}\rceil,\lceil(1-\epsilon^{\prime})^{2}\rceil,\lceil(1-\epsilon^{\prime})^{3}\rceil,\ldots,n\\}$
we only consider minimal (rightmost or topmost) segments that end at
$c^{\prime}$ and their LIS is at least $v$. There are at most $O(\log
n/\epsilon^{\prime})$ vertical and at most $O(\log n/\epsilon^{\prime})$ such
horizontal segments and each one can be found via a binary search in time
$O(\log^{2}n)$ (an $O(\log n)$ overhead for binary search and an $O(\log n)$
overhead for finding the LIS of a potential solution). Thus, if we only
consider these segments, the runtime improves to
$O(\log^{3}n/\epsilon^{\prime})$ for each pair of cells $(c,c^{\prime\prime})$
which in total amounts to a runtime of $O(m^{4}\log^{3}n/\epsilon^{\prime})$.

$c$$c^{\prime}$ Figure 17: An example is shown for computing the value of
$g(c^{\prime})$. Candidate horizontal segments are colored in red and
candidate vertical segments are colored in green. When we use each of the
candidate segments in our dynamic program, we update the solution based on the
computed value for the corresponding blue cell.

The correctness of this case is easy. Assume that the optimal segment that
gives us the highest value for $g(c^{\prime})$ in Algorithm 1 is a horizontal
segment $s_{1}$, but we do not consider $s_{1}$ in the improved algorithm. Let
$v$ be the largest value in sequence $\mathbb{D}$ which is not larger than the
LIS of $s_{1}$. Let the corresponding horizontal segment for value $v$ in our
algorithm be $s_{2}$. We define $c^{\prime\prime}_{1},c^{\prime\prime}_{2}$ as
the cells to the left and bottom of $s_{1}$ and $s_{2}$ respectively. It
follows from our algorithm that $s_{2}$ is not larger than $s_{1}$ and thus
the value we store for $g(c^{\prime\prime}_{2})$ is at least as large as
$g(c^{\prime\prime}_{1})$. Moreover, we have
$\textsf{LIS}(s^{\prime\prime}_{2})\geq(1-\epsilon^{\prime})\textsf{LIS}(s^{\prime\prime}_{1})$
and in the update process we only lose an $\epsilon^{\prime}$ fraction of the
LIS of the last segment. The same analysis works for vertical segments as
well. This implies that our estimation for $g$ loses a factor of at most
$(1-\epsilon^{\prime})$ throughout the DP.

$c$$c^{\prime}$$c^{\prime\prime}_{1}$$c^{\prime\prime}_{2}$$s_{1}$$s_{2}$$g(c^{\prime\prime}_{2})\
\geq\ g(c^{\prime\prime}_{1})$$\textsf{LIS}(s2)\ \geq\ (1-\epsilon^{\prime})\
\textsf{LIS}(s_{1})$ Figure 18: If we use segment $s_{2}$ instead of segment
$s_{1}$, we only lose a factor of $1-\epsilon^{\prime}$ in the approximation.

For $\Delta=2$, we first consider all 1-multisegments (segments) as explained
above and determine an initial value for $g(c^{\prime})$. Then we proceed by a
generalization of the above idea for $2$-multisegments. Let
$\mathbb{D}=\\{1,\lceil
1-\epsilon^{\prime}\rceil,\lceil(1-\epsilon^{\prime})^{2}\rceil,\lceil(1-\epsilon^{\prime})^{3}\rceil,\ldots,n\\}$.
For any two values $v_{1},v_{2}\in\mathbb{D}$ we consider the following
$2$-multisegment: We define a sweeping line which is initially equal to the
right edge of cell $c^{\prime}$. We move the sweeping line parallel to that
edge to the left, until the LIS of the rectangle which is covered by the first
sweeping line is at least $v_{1}$. Let $e$ be the cell that contains the
sweeping line. Now, we define another sweeping line which is equal to the
portion of the bottom edge of $e$ which is not covered by the first sweeping
line. Starting from there, we move the second sweeping line parallel to that
edge downward, until the LIS of the corresponding rectangle becomes at least
$v_{2}$ (See Figure 19 for a visualization of the two rectangles). We define
2-multisegment $S$ as the set of all the cells that intersect with either
rectangles and estimate its LIS by $v_{1}+v_{2}$. Next, we determine cell
$c^{\prime\prime}$ which is to the left and bottom of $S$ and update the value
of $g(c^{\prime})$ as
$g(c^{\prime}):=\max\\{g(c^{\prime}),g(c^{\prime\prime})+v_{1}+v_{2}\\}$.
Similarly we repeat the same procedure starting with vertical and then
horizontal rectangles. The total number of segments that we investigate via
this algorithm is $2|D|^{2}=O(\log^{2}n/\epsilon^{\prime 2})$ and finding each
segment takes time $O(\log^{2}n)$. Thus, the update time becomes
$O(\log^{4}n/\epsilon^{\prime 2})$ for each pair of cells $(c,c^{\prime})$ and
$O(m^{4}\log^{4}n/\epsilon^{\prime 2})$ in total.

$c$$c^{\prime}$$\textsf{LIS}\ =\ v_{1}$$\textsf{LIS}\ =\ v_{2}$$S$ Figure 19:
This figure shows how a segment $S$ is made by two value $v_{1}$ and $v_{2}$.
The solution is then updated based on the DP value for the blue cell plus
$v_{1}+v_{2}$. Purple rectangles are made by sweeping lines that move to the
left for the top rectangle and move down for the bottom rectangle.
$c$$c^{\prime}$$\textsf{LIS}(R_{1})\ =\ v_{1}$$\textsf{LIS}(R_{2})\ =\
v_{2}$$S^{\prime}$$d^{\prime}$$d$$R_{1}$$R_{2}$ Figure 20: If $R_{1}$ does not
touch the entire horizontal part of $S^{\prime}$, then a single segment that
contains $R_{1}$ can be used to updated $g(c^{\prime})$.

We prove in the following that by doing so, we only lose a factor of at most
$1-\epsilon^{\prime}$ in the approximation. Similar to previous discussion,
let $S^{\prime}$ be the last multisegment that is used in Algorithm 1 to
update the value of $g(c^{\prime})$. If $S^{\prime}$ fits in a row or column
(meaning it is a segment), then the proof follows from our previous
discussion. Thus, without loss of generality, we assume that $S^{\prime}$
consists of a horizontal segment (on top) and a vertical segment (on the
bottom). Let $v^{\prime}_{1}$ be the contribution of the top horizontal part
of $S^{\prime}$ to the LIS of $S^{\prime}$ and $v^{\prime}_{2}$ be the
contribution of the remainder of $S^{\prime}$ to $\textsf{LIS}(S^{\prime})$.
We define $v_{1}$ and $v_{2}$ as the largest numbers in set $\mathbb{D}$ that
are bounded by $v^{\prime}_{1}$ and $v^{\prime}_{2}$, respectively. In our
algorithm, we consider pair of values $(v_{1},v_{2})$ for constructing a
2-multisegment in the following way: we first make a rectangle via a sweeping
line that moves horizontally from $c^{\prime}$ to the left. We do the same
thing downward for $v_{2}$. Let the two rectangles be $R_{1}$ and $R_{2}$. If
rectangle $R_{1}$ does not touch the top-left cell of $S^{\prime}$, then
$g(c^{\prime})$ can be updated via a segment with parameter $v_{1}$ (see
Figure 20). This is because without the horizontal part of $S^{\prime}$, the
LIS of the remainder of $S$ is at least $v^{\prime}_{2}$. Thus, if we define
$d^{\prime}$ as the topmost part of $S^{\prime}$ which is not in its
horizontal part, then $g(d^{\prime})\geq g(c^{\prime})-v^{\prime}_{1}$ holds.
Thus, if we define $d$ to be the cell to the left and bottom of $R_{1}$ then
$g(d)\geq g(d^{\prime})\geq g(c^{\prime})-v^{\prime}_{1}$. Thus, we only lose
a $1-\epsilon^{\prime}$ factor if we update the value of $g(c^{\prime})$ from
a segment with parameter $v_{1}$.

If $R_{1}$ touches the entire horizontal part of $S$, then $R_{2}$ also falls
within $S^{\prime}$ and therefore, the 2-multisegment that our algorithm
constructs will be entirely inside $S^{\prime}$. Moreover, the LIS of the
2-multisegment that our algorithm makes is at least
$v_{1}+v_{2}\geq(1-\epsilon^{\prime})(v^{\prime}_{1}+v^{\prime}_{2})$. Thus,
we only lose a factor $1-\epsilon^{\prime}$ in our estimation.

This approach is generalizable to larger $\Delta$. In order to update the
value for $g(c^{\prime})$, for any tuple of $\Delta$ elements
$v_{1},v_{2},\ldots,v_{\Delta}\in\mathbb{D}$ we construct a
$\Delta$-multisegment by making $\Delta$ rectangles and we estimate the value
of the segment by the summation of the LIS of the rectangles. Next, we update
the value of $g(c^{\prime})$ from the constructed segment. This takes time
$O(\Delta m^{4}\log^{\Delta+2}n/\epsilon^{\prime\Delta})$ since making each
$\Delta$-multisegment takes time $O(\Delta\log^{2}n)$. The proof for the
correctness of the approximation factor is similar to the proof explained
above for $2$-multisegments.

$c$$c^{\prime}$$\textsf{LIS}\ =\ v_{1}$$\textsf{LIS}\ =\
v_{2}$$S$$\textsf{LIS}\ =\ v_{3}$ Figure 21: This figure shows how the
discretization idea generalizes to $3$-multisegments.

After a preprocessing time of $O(\Delta
m^{4}\log^{\Delta+2}n/\epsilon^{\prime\Delta})$, for every pair of table
cells, we have a $(1-\epsilon^{\prime})\frac{\Delta-1}{\Delta}\geq 1-\epsilon$
approximation of the LIS of the points included in the rectangle between the
two corners. We show that using this information, we will be able to answer
each query in time $O(\log^{2\Delta+2}/\epsilon^{\prime 2\Delta+2})$. The idea
is similar to what we do above. Again, we consider solutions made by non-
conflicting multisegments. The only difference is that we only take into
account the points that lie inside the given query rectangle. Moreover,
instead of $\Delta$-multisegments, we consider $(\Delta+1)$-multisegments
here. Since we already have a desirable estimation for any rectangle that
starts from a table cell and ends at another table cell, we only need to fix
the bottom-left and top-right multisegment. By using the above idea, we can
construct $O(\log^{\Delta+1}n/\epsilon^{\prime\Delta+1})$ different candidate
$(\Delta+1)$-multisegments for bottom-left and
$O(\log^{\Delta+1}n/\epsilon^{\prime\Delta+1})$ different candidate
$(\Delta+1)$-multisegments for top-right corner which amounts to
$O(\log^{2\Delta+2}n/\epsilon^{\prime 2\Delta+2})$ combinations. Thus, we can
obtain an $\frac{\Delta-1}{\Delta}1-\epsilon^{\prime}\geq 1-\epsilon$
approximation of the solution in time $O(\log^{2\Delta+2}n/\epsilon^{\prime
2\Delta+2})$. Notice that once we fix the bottom-left and top-right
multisegments, the solution for the area between them is already available.

The reason we use $(\Delta+1)$-multisegments instead of $\Delta$-multisegments
is the following: consider the optimal non-conflicting $\Delta$-multisegments
that provide the solution for a query. They may not necessarily cover the
bottom-left and top-right corners of the query-rectangle. By using
$(\Delta+1)$-multisegments, we can simply modify the optimal non-conflicting
$\Delta$-multisegments to cover both corners as well.

$\textsf{LIS}\ =\ v_{1}$$\textsf{LIS}\ =\ v_{2}$$\textsf{LIS}\ =\
v_{3}$$\textsf{LIS}\ =\ v^{\prime}_{1}$$\textsf{LIS}\ =\ v^{\prime}_{2}$
Figure 22: A solution is made for a query by using a $2$-multisegment for the
bottom-left corner and a $3$-multisegment for the top-right corner. A
$1-\epsilon$ approximate solution is already known for the gray area of the
table. Moreover, we use parameters $\langle
v^{\prime}_{1},v^{\prime}_{2}\rangle$ for the bottom-left multisegment and
parameters $\langle v_{1},v_{2},v_{3}\rangle$ for the top-right multisegment
and thus we approximate their LCS by $v^{\prime}_{1}+v^{\prime}_{2}$ and
$v_{1}+v_{2}+v_{3}$. Therefore, our total estimate for this construction is
$v_{1}+v_{2}+v_{3}+v^{\prime}_{1}+v^{\prime}_{2}$ plus the estimated solution
for the gray area.

In Theorem 33 we elaborate more on the above idea to show that we can
approximate the query-LIS problem within a factor $1-\epsilon$ with near
linear preprocessing time and polylogarithmic query time.

######  Theorem 33.

For any $0<\epsilon,\kappa$, query-LIS can be approximated within a factor
$1-\epsilon$ with preprocessing time $O((\log{1/\kappa}\log
n/\epsilon)^{O((\log 1/\kappa)^{2}/\epsilon)}n^{1+\kappa})$ and query time
$O((\log{1/\kappa}\log n/\epsilon)^{O((\log 1/\kappa)^{2}/\epsilon)})$.

###### Proof.

We discussed how to use extended grid packing to improve the naive algorithm
with $\widetilde{O}(n^{5})$ preprocessing time to an algorithm with
$\widetilde{O}(n^{5/2})$ preprocessing time. The drawback is adding a
$1-\epsilon$ multiplicative factor to the approximation guarantee and a
polylogarithmic multiplicative factor to the runtime of answering each query.
We use the same idea to further improve the preprocessing time down to
$\widetilde{O}_{\epsilon,\kappa}(n^{1+\kappa})$. To this end, we define
$k=\lceil 3\log 1/\kappa\rceil+5$ and $\epsilon^{\prime}=\epsilon/(2k)$.

algorithm | preprocessing time | $m$ | $q_{i}$ | $\frac{q_{i+1}-1}{q_{i}-1}$
---|---|---|---|---
$\mathcal{A}_{0}$ | $\widetilde{O}(n^{5})$ | - | 5 |  $\simeq$ 0.375
$\mathcal{A}_{1}$ | $\widetilde{O}(n^{5/2})$ | $n^{5/8}$ | 2.5 |  $\simeq$ 0.5454
$\mathcal{A}_{2}$ | $\widetilde{O}(n^{20/11})$ | $n^{5/11}$ |  $\simeq$ 1.818 |  $\simeq$0.6226
$\mathcal{A}_{3}$ | $\widetilde{O}(n^{80/53})$ | $n^{20/53}$ |  $\simeq$ 1.509 |  $\simeq$0.6652
$\mathcal{A}_{4}$ | $\widetilde{O}(n^{320/239})$ | $n^{80/239}$ |  $\simeq$ 1.338 |  $\simeq$ 0.6914
$\mathcal{A}_{5}$ | $\widetilde{O}(n^{1280/1037})$ | $n^{320/1037}$ |  $\simeq$ 1.234 |  $\simeq$ 0.7084
$\mathcal{A}_{6}$ | $\widetilde{O}(n^{5120/4391})$ | $n^{1280/4391}$ |  $\simeq$ 1.166 |  $\simeq$ 0.7201
$\mathcal{A}_{7}$ | $\widetilde{O}(n^{20480/18293})$ | $n^{5120/18293}$ |  $\simeq$ 1.119 |  $\simeq$ 0.7282
$\mathcal{A}_{8}$ | $\widetilde{O}(n^{81920/75359})$ | $n^{20480/75359}$ |  $\simeq$ 1.087 |  $\simeq$ 0.7340
$\mathcal{A}_{9}$ | $\widetilde{O}(n^{327680/307997})$ | $n^{81920/307997}$ |  $\simeq$ 1.063 |  $\simeq$ 0.7382
$\mathcal{A}_{10}$ | $\widetilde{O}(n^{1310720/1251671})$ | $n^{327680/1251671}$ |  $\simeq$ 1.047 |  $\simeq$ 0.7412
Table 2: $q_{i}$ is the exponent of $n$ in the preprocessing time of Algorithm
$\mathcal{A}_{i}$.

We denote the naive algorithm (with preprocessing time $O(n^{5}\log n)$) by
$\mathcal{A}_{0}$. Each time, we use a similar technique as explained above to
obtain an improved algorithm $\mathcal{A}_{i}$ from $\mathcal{A}_{i-1}$. The
construction of $\mathcal{A}_{1}$ from $\mathcal{A}_{0}$ is already discussed.
The only parameter of the construction that changes for new algorithms is the
value of $m$. To be precise, let $q_{i}$ be the exponent of $n$ in the
preprocessing time of Algorithm $\mathcal{A}_{i}$ and $r_{i}$ be $\log m/\log
n$ when we use $\mathcal{A}_{i-1}$ to construct $\mathcal{A}_{i}$. As
explained, we have $q_{0}=5$. For each $0\leq i$, we set
$r_{i+1}=q_{i}/(q_{i}+3)$ and $q_{i+1}=r_{i+1}+q_{i}(1-r_{i+1})$. There are
two steps in the preprocessing phase of Algorithm $\mathcal{A}_{i+1}$. In the
first step, we construct a grid and make $2m$ subproblems and for each
subproblem we use $\mathcal{A}_{i}$. Thus, the runtime of the first step is

$\widetilde{O}_{\epsilon,\kappa}(m(n/m)^{q_{i}})=\widetilde{O}_{\epsilon,\kappa}(n^{r_{i+1}}n^{q_{i}}/(n^{r_{i+1}})^{q_{i}})=\widetilde{O}_{\epsilon,\kappa}(n^{r_{i+1}+q_{i}(1-r_{i+1})}).$

The second step of preprocessing is constructing an approximate solution for
$O(m^{4})$ subproblems each in polylogarithmic time (the exponent of the log
factor may depend on $1/\epsilon$ or $1/\kappa$). This takes time
$\widetilde{O}_{\epsilon,\kappa}(n^{4r_{i+1}})$. Since
$r_{i+1}=q_{i}/(q_{i}+3)$ then we have

$\begin{split}r_{i+1}+q_{i}(1-r_{i+1})&=q_{i}/(q_{i}+3)+q_{i}(1-(q_{i}/(q_{i}+3)))\\\
&=q_{i}(1/(q_{i}+3)+(1-(q_{i}/(q_{i}+3))))\\\
&=q_{i}(1/(q_{i}+3)+(3/(q_{i}+3)))\\\ &=q_{i}(4/(q_{i}+3))\\\
&=4q_{i}/(q_{i}+3)\\\ &=4r_{i+1}\end{split}$

and therefore the preprocessing time of Algorithm $\mathcal{A}_{i+1}$ would be
bounded by
$\widetilde{O}_{\epsilon,\kappa}(n^{r_{i+1}+q_{i}(1-r_{i+1})})=\widetilde{O}_{\epsilon,\kappa}(n^{q_{i+1}})$.

Table 2 presents the runtime of each algorithm along with parameters that we
use for its construction.

By this construction, we always have

$\begin{split}\frac{q_{i+1}-1}{q_{i}-1}&=\frac{r_{i+1}+q_{i}(1-r_{i+1})-1}{q_{i}-1}\\\
&=\frac{q_{i}/(q_{i}+3)+q_{i}(1-q_{i}/(q_{i}+3))-1}{q_{i}-1}\\\
&=\frac{q_{i}/(q_{i}+3)+q_{i}(3/(q_{i}+3))-1}{q_{i}-1}\\\
&=\frac{4q_{i}/(q_{i}+3)-1}{q_{i}-1}\\\
&=\frac{(3q_{i}-3)/(q_{i}+3)}{q_{i}-1}\\\ &=\frac{3}{q_{i}+3}\\\ &\leq
3/4.\end{split}$

where the last inequality follows from the fact that $1<q_{i}$. Therefore
after $k$ levels of recursive calls, the exponent of $n$ in the preprocessing
step of Algorithm $A_{k}$ is smaller than $1+\kappa$. This implies that the
overall preprocessing time is bounded by
$\widetilde{O}_{\epsilon,\kappa}(n^{1+\kappa})$. Moreover, by defining
$\Delta=\lceil 1/\epsilon^{\prime}\rceil$, in each level of recursion we lose
a factor of at most $(1-\epsilon^{\prime})^{2}$ in the approximation and thus
in total the approximation factor is at least $(1-\epsilon^{\prime})^{2k}\geq
1-\epsilon$. Query time for $\mathcal{A}_{0}$ is $O(\log n)$ and in each level
of recursion, there is a multiplicative $O((\log
n/\epsilon^{\prime})^{2k/\epsilon+2k})$ overhead and thus the query time as
well as the preprocessing time is multiplied by $O((\log{1/\kappa}\log
n/\epsilon)^{O((\log 1/\kappa)^{2}/\epsilon)})$ for $\mathcal{A}_{k}$. ∎

###  4.3 A Dynamic Solution for LIS

We present a dynamic algorithm for LIS that approximates the solution within a
$1-\epsilon$ multiplicative factor. This is achieved by using extended grid
packing. For the purpose of our technique, we generalize the problem in the
following way: In the original dynamic problem, our goal is to maintain an
approximation to the size of the longest increasing subsequence. Thus after
each operation, one needs to update the solution size and therefore, we can
simply assume that after each update the size of the LIS is desired. In our
generalization, we still consider the same set of operations. However, our
algorithm is required to answer a stronger type of queries: Assuming that we
describe the sequence as points on the plane (as discussed earlier), for each
query, we provide a rectangle with edges parallel to the axis lines and the
algorithm should give us an estimate for the LIS of the points inside the
rectangle. This is similar to the queries that we consider in the query-LIS
problem.

Since in the previous setting, we only asked the size of the longest
increasing subsequence, one could argue that after each update, there is at
most one question to be answered. In our new setting, we may need to answer
multiple queries after each update and thus it makes sense to separate the
concept of query from operations. That is, we may be able to answer each query
faster than the time which our algorithm requires for updating the sequence.
Thus in our setting, we define the update time to be the time our algorithm
needs to update the sequence after an operation arrives and the query time to
be the time our algorithm needs to answer a query. We show in the following
that we can answer each query faster than the update time and this is an
important part of the analysis.

We show that for any $0<\epsilon,\kappa$ our algorithm is able to provide a
$1-\epsilon$ approximation of the solution with update time
$\widetilde{O}_{\epsilon,\kappa}(n^{\kappa})$ and query time
$\widetilde{O}_{\epsilon,\kappa}(1)$. Recall that
$\widetilde{O}_{\epsilon,\kappa}$ hides all the factors that depend only on
$\epsilon$, $\kappa$, or $\log n$. An exact dynamic solution for LIS with
update time $O(n^{5}\log n)$ and query time $O(\log n)$ follows from the
straightforward algorithm discussed in Section 4.2. In other words, if after
every operation, we compute the solution for all possible rectangles that can
be given to the algorithm as a query, then we can answer each query in time
$O(\log n)$. Moreover, since there are at most $O(n^{4})$ rectangles that
cover distinct sets of points, we can update the solution in time $O(n^{5}\log
n)$ each time an operation arrives. Notice that after answering a query, we do
not require to update the solution. To improve the update time, we use the
notion of block-based algorithms [MS20]. Roughly speaking, if we design a
block-based algorithm whose bound over the update time is amortized, we can
then turn the block-based algorithm into an equivalent dynamic algorithm with
a worst-case bound on its update time.

For a block-based algorithm, we start with an initial sequence of size $n$.
Our algorithm is then allowed to preprocess the input in time $f(n)$. After
the preprocessing step, our block-based algorithm is responsible for $g(n)$
operations and all the queries that come prior to the last operation. After
$g(n)$ operations, our algorithm terminates. Mitzenmacher and Seddighin [MS20]
prove that if the block-based algorithm performs each operations in time
$h(n)$ in the worst case, then it can be transformed into a dynamic algorithm
whose worst-case update time is $O(f(n)/g(n)+h(n))$. The approximation factor
of the dynamic algorithm is exactly the same as the block-based algorithm and
also the query time remains asymptotically the same. Since Mitzenmacher and
Seddighin [MS20] use a slightly different setting in which queries and
operations are treated equivalently, we bring a formal proof for our
discussion in Appendix A.

To improve the naive algorithm, we design a block-based algorithm with
preprocessing time $f(n)=O(n^{19/7}\log n)$, $g(n)=n^{3/7}$, and
$h(n)=\widetilde{O}_{\epsilon}(n^{16/7})$. In the preprocessing step, we
construct a grid of size $m\times m$ where $m=n^{4/7}$. Rows and columns of
our grid evenly divide the points and thus each row or column covers
$O(n^{3/7})$ points. Similar to what we discussed in Section 4.2, we make $2m$
subproblems for dynamic LIS where each subproblem is concerned with the subset
of points that is covered by the corresponding row or the corresponding column
of the grid. The construction of the grid only requires to sort the points
based on $x$ and $y$ coordinates and thus we can do it in time $O(n\log n)$.
Moreover, each subproblem includes $O(n^{3/7})$ points and therefore
precomputing the solutions for all possible rectangles within each subproblem
takes time $O(n^{15/7}\log n)$. Since we run this procedure for all $2m$
subproblems, processing time is $O(n^{19/7}\log n)$.

Figure 23: The red snake lines show the grid and yellow and blue boxes present
the points included in each of the subproblems. Patterned boxes specify the
subproblems that are affected by an operation.

Due to our construction, each time an operation arrives, there is only one row
and one column which is affected by the modification. Also, since the size of
each subproblem (the number of points covered by each row or column) is
bounded by $O(n^{3/7})$ then by precomputing the solution for all possible
rectangles, we can update the entries for each subproblem in time
$O(n^{15/7}\log n)$. In addition to updating the solution for each subproblem,
we also maintain a table of size $m^{2}\times m^{2}$ that keeps an
approximation to the value of LIS for each rectangle formed by the cells of
the grid. As discussed in Section 4.2, using the extended grid packing, we can
approximate the solution for each rectangle within a factor $1-\epsilon$ and
doing this for all possible rectangles takes time
$\widetilde{O}_{\epsilon}(m^{4})$. Therefore, after each operation, we update
our table in time
$\widetilde{O}_{\epsilon}(m^{4})=\widetilde{O}_{\epsilon}(n^{16/7})$. Similar
to the algorithm of Section 4.2, each query can be approximated via the
precomputed solutions for the rectangles and the solutions for subproblems in
time $\widetilde{O}_{\epsilon}(1)$. Since $g(n)=n^{3/7}$, we are sure that
after $g(n)$ operations, the size of each subproblem remains bounded by
$O(n^{3/7})$ and thus the runtimes do not increase asymptotically as
operations add new points to the subproblems. Therefore, our block-based
algorithm has preprocessing time $f(n)=O(n^{19/7}\log n)$, $g(n)=n^{3/7}$, and
$h(n)=\widetilde{O}_{\epsilon}(n^{16/7})$. This leads to a dynamic solution
with worst-case update time $\widetilde{O}_{\epsilon}(n^{16/7})$ and
approximation factor $1-\epsilon$. Also, the query complexity of our dynamic
algorithm is $\widetilde{O}_{\epsilon}(1)$.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$(7,2,4\
|\ 1,9,6\ |\ 3,5,8)$$(7,2,4\ |\
1,9,\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0},6\
|\ 3,5,8)$ Figure 24: An example for adding an element to the array.

Since inserting elements to the sequence or removing elements from the
sequence may change the indices of other elements, the points on the plane are
subject to moves. Each time an operation arrives, we update the solution for
the corresponding subproblems. Let us be more specific about this. Initially,
$m-1$ vertical lines divide the array into chunks of size roughly $n/m$. As
operations arrive, the elements are shifted to the left or to the right (their
indices are updated). Each vertical line can be thought of as a separator
between two consecutive elements that is also shifted to the left or to the
right when elements are added or removed. Thus, although the vertical lines
move, each element which is inserted or deleted lies between two thresholds
and corresponds to a unique column of the grid. The corresponding row is
uniquely determined by the horizontal lines (those lines remain unchanged).
Thus, every element insertion or deletion affects only one cell of the grid
which is included in at most two subproblems. Mitzenmacher and Seddighin
[MS20] show that the shifts can be efficiently done by an $O(\log n)$ overhead
in the runtime of the algorithm. More precisely, they give a data structure
that is able to insert and delete elements from the sequence while giving
access to any position of the sequence in time $O(\log n)$. We use the same
data structure and therefore we incorporate an additional $O(\log n)$ overhead
in the runtime of our dynamic algorithms.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$0$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$\langle
7,2,4\ |\ 1,9,6\ |\ 3,5,8\rangle$$\langle 7,2,4\ |\ 1,6\ |\ 3,5,8\rangle$
Figure 25: An example for removing an element from the array.

In what follows, we bring a recursive application of the above ideas that
leads to a solution with update time
$\widetilde{O}_{\epsilon,\kappa}(n^{\kappa})$ and approximation factor
$1-\epsilon$ for arbitrarily small $0<\epsilon,\kappa$. The query time of our
algorithm is $\widetilde{O}_{\epsilon,\kappa}(1)$.

######  Theorem 34.

For any $0<\epsilon,\kappa$, there exists a dynamic algorithm for LIS with
worst-case update time $O((\log
n/(\epsilon\kappa))^{O(1/(\epsilon\kappa^{2}))}n^{\kappa})$ and approximation
factor $1-\epsilon$ and query time $O((\log
n/(\epsilon\kappa))^{O(1/(\epsilon\kappa^{2}))})$.

###### Proof.

Similar to the proof of Theorem 33, we construct several algorithms which we
denote by $\mathcal{A}_{0},\mathcal{A}_{1},\mathcal{A}_{2},\ldots$ and
$\mathcal{A}^{\prime}_{1},\mathcal{A}^{\prime}_{2},\mathcal{A}^{\prime}_{3},\ldots$.
Each $\mathcal{A}^{\prime}_{i}$ represents a block-based algorithm and each
$\mathcal{A}_{i}$ is a dynamic algorithm. We begin by a dynamic algorithm
$\mathcal{A}_{0}$ for LIS with preprocessing and update times
$\widetilde{O}_{\epsilon,\kappa}(n^{1+\kappa/2})$ and query time
$\widetilde{O}_{\epsilon,\kappa}(1)$. $\mathcal{A}_{0}$ basically uses the
non-dynamic algorithm of Theorem 33 to update the sequence after each
operation. At each step, we first construct $\mathcal{A}^{\prime}_{i+1}$ from
$\mathcal{A}_{i}$ and then using the reduction of [MS20], we turn
$\mathcal{A}^{\prime}_{i+1}$ into a dynamic algorithm $\mathcal{A}_{i+1}$.

As shown by Mitzenmacher and Seddighin [MS20], if we construct a dynamic
algorithm $\mathcal{A}$ from a block-based algorithm $\mathcal{A}^{\prime}$
then in order to initialize $\mathcal{A}$ for a sequence of length $n$, we
only need to spend preprocessing time $f(n)$ corresponding to
$\mathcal{A}^{\prime}$. For constructing $\mathcal{A}^{\prime}_{i+1}$ from
$\mathcal{A}_{i}$ we set $m=n^{\kappa/4}$. In the construction block-based
algorithm $\mathcal{A}^{\prime}_{i+1}$, we set
$f(n)=\widetilde{O}_{\epsilon,\kappa}(n^{1+\kappa/2})$, $g(n)=n^{1-\kappa/4}$
and
$h(n)=\widetilde{O}_{\epsilon,\kappa}(n^{\kappa}+n^{(1+\kappa/2)(1-\kappa/4)^{i+1}})$.
As a result, the update time of our dynamic algorithm $\mathcal{A}_{i+1}$ is
always bounded by
$\widetilde{O}_{\epsilon,\kappa}(n^{\kappa}+n^{(1+\kappa/2)(1-\kappa/4)^{i+1}})$.
Each time we construct a grid and divide the problem into smaller subproblems
as explained above. In what follows, we analyze the time bounds.

To initialize Algorithm $\mathcal{A}^{\prime}_{i+1}$, we draw a grid of size
$n^{\kappa/4}\times n^{\kappa/4}$ in time $O(n\log n)$ in a way that each row
and each column covers $O(n^{1-\kappa/4})$ points. Then, for each row and
column we use Algorithm $\mathcal{A}_{i}$ to initialize a solution for the
corresponding subproblem. Since for $\mathcal{A}_{0}$ the initialization time
is $\widetilde{O}_{\epsilon,\kappa}(n^{1+\kappa/2})$, the same bound carries
over to the preprocessing times of all other algorithms
$\mathcal{A}^{\prime}_{1},\mathcal{A}^{\prime}_{2},\ldots$ (The initialization
times can only improve as we increase $i$). Also, since $m=n^{\kappa/4}$ the
$\widetilde{O}_{\epsilon,\kappa}(m^{4})$ part of the preprocessing time is
dominated by the $\widetilde{O}_{\epsilon,\kappa}(n^{1+\kappa/2})$ term in the
preprocessing time.

For each $\mathcal{A}_{i+1}$, in order to update the solution, we need to
update the subproblems concerning the corresponding row and the corresponding
column. Since each row and each column cover at most $O(n^{1-\kappa/4})$
elements, then this implies that the update time $h(n)$ for
$\mathcal{A}^{\prime}_{1}$ is equal to
$\widetilde{O}_{\epsilon,\kappa}(n^{\kappa}+(n^{1-\kappa/4})^{1+\kappa/2})$.
Moreover, since for $\mathcal{A}_{1}$, the dominant term in $f(n)/g(n)+h(n)$
is $h(n)$, this implies that the update time of the dynamic Algorithm
$\mathcal{A}_{i}$ is equal to
$\widetilde{O}_{\epsilon,\kappa}(n^{\kappa}+(n^{1-\kappa/4})^{1+\kappa/2})$.
Thus, we can inductively prove that for each $i\geq 1$, the update time for
block-based algorithm $\mathcal{A}^{\prime}_{i}$ is equal to the update time
of the dynamic algorithm $\mathcal{A}_{i}$ which is bounded by
$\widetilde{O}_{\epsilon,\kappa}(n^{\kappa}+(n^{(1+\kappa/2)(1-\kappa/4)^{i}})$.
By setting $k=\lceil 20/{\kappa}\rceil$, we can be sure that the update time
of Algorithm $\mathcal{A}_{k}$ is bounded by
$\widetilde{O}_{\epsilon,\kappa}(n^{\kappa})$. Also, the query time remains
$\widetilde{O}_{\epsilon,\kappa}(1)$ for all the algorithms.

In what follows, we discuss the approximation factor and the runtimes that are
suppressed by the $\widetilde{O}_{\epsilon,\kappa}$ notation. We set the
approximation factor of our first algorithm $\mathcal{A}_{0}$ equal to
$1-\epsilon/2$ and for the rest of the constructions we use
$\epsilon^{\prime}=\epsilon/(40k)$. Thus, the overall approximation factor
will be $(1-\epsilon/2)(1-\epsilon^{\prime})^{k}\geq 1-\epsilon$. This also
adds a multiplicative overhead $O(\log
n/(\epsilon\kappa))^{O(1/(\epsilon\kappa))}$ to the preprocessing time, update
time, and query time of each level of recursion and therefore the update time
for the final algorithm would be $O((\log
n/(\epsilon\kappa))^{O(1/(\epsilon\kappa^{2}))}n^{\kappa})$.

∎

By setting $\kappa=1/(\log n)^{1/3}$ in Theorem 34, we obtain an algorithm
with update time

$O((\log n/\epsilon)^{O((\log n)^{2/3}/\epsilon)}).$

Since in this case the query time and update time are equal, we can use this
algorithm for the original dynamic problem wherein the queries and the
operations are treated the same way.

######  Theorem 35 (a corollary of Theorem 34).

For any $0<\epsilon$, there exists a dynamic algorithm for LIS with worst-case
update time $O((\log n/\epsilon)^{O((\log n)^{2/3}/\epsilon)})$ and
approximation factor $1-\epsilon$.

## References

  * [ACCL04] Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu.  Estimating the distance to a monotone function.  In RANDOM, 2004.
  * [AKM+87] Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber.  Geometric applications of a matrix-searching algorithm.  Algorithmica, 2:195–208, 1987.  doi:10.1007/BF01840359.
  * [AOSS18] Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon.  Fully dynamic maximal independent set with sublinear update time.  In STOC, 2018.
  * [AOSS19] Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon.  Fully dynamic maximal independent set with sublinear in n update time.  In SODA, 2019.
  * [BDH+19] Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan.  Fully dynamic maximal independent set with polylogarithmic update time.  In FOCS, 2019.
  * [BEG+18] Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin.  Approximating edit distance in truly subquadratic time: quantum and MapReduce.  In SODA, 2018.
  * [CCP13] Alex Chen, Timothy Chu, and Nathan Pinsker.  The dynamic longest increasing subsequence problem.  arXiv preprint arXiv:1309.7724, 2013.
  * [CGP20] Panagiotis Charalampopoulos, Paweł Gawrychowski, and Karol Pokorski.  Dynamic longest common substring in polylogarithmic time.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, ICALP, volume 168 of LIPIcs, pages 27:1–27:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ICALP.2020.27.
  * [CKM20] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Shay Mozes.  Dynamic string alignment.  In Inge Li Gørtz and Oren Weimann, editors, CPM, volume 161 of LIPIcs, pages 9:1–9:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.CPM.2020.9.
  * [CP10] Timothy M. Chan and Mihai Pătraşcu.  Counting inversions, offline orthogonal range counting, and related problems.  In Moses Charikar, editor, 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pages 161–173. SIAM, 2010.  doi:10.1137/1.9781611973075.15.
  * [DGL+99] Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky.  Improved testing algorithms for monotonicity.  In RANDOM-APPROX, 1999.
  * [EKK+98] Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan.  Spot-checkers.  In STOC, 1998.
  * [Fis01] Eldar Fischer.  The art of uninformed decisions.  Bulletin of the EATCS, 75:97, 2001.
  * [FR06] Jittat Fakcharoenphol and Satish Rao.  Planar graphs, negative weight edges, shortest paths, and near linear time.  J. Comput. Syst. Sci., 72(5):868–889, 2006.  doi:10.1016/j.jcss.2005.05.007.
  * [Fre75] Michael L Fredman.  On computing the length of longest increasing subsequences.  Discrete Mathematics, 11(1):29–35, 1975.
  * [GG07] Anna Gál and Parikshit Gopalan.  Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence.  In FOCS, 2007.
  * [GJ20] Paweł Gawrychowski and Wojciech Janczewski.  Fully dynamic approximation of lis in polylogarithmic time, 2020.  arXiv:2011.09761.
  * [GJKK07] Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar.  Estimating the sortedness of a data stream.  In SODA, 2007.
  * [GKK+18] Paweł Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Łacki, and Piotr Sankowski.  Optimal dynamic strings.  In SODA, 2018.
  * [HKNS15] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In STOC, 2015.
  * [HSSS19] MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Xiaorui Sun.  Approximating lcs in linear time: Beating the barrier.  In SODA, 2019.
  * [IMS17] Sungjin Im, Benjamin Moseley, and Xiaorui Sun.  Efficient massively parallel methods for dynamic programming.  In STOC, 2017.
  * [LOP+15] Jakub Lacki, Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski, and Anna Zych.  The power of dynamic distance oracles: Efficient dynamic algorithms for the steiner tree.  In STOC, 2015.
  * [MS20] Michael Mitzenmacher and Saeed Seddighin.  Dynamic algorithms for LIS and distance to monotonicity.  In STOC, 2020.
  * [MS21] Michael Mitzenmacher and Saeed Seddighin.  Improved sublinear time algorithms for longest increasing subsequence.  In SODA, 2021.
  * [NS17] Danupon Nanongkai and Thatchaphol Saranurak.  Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o(n${}^{\mbox{1/2 - {$\epsilon$}}}$)-time.  In STOC, 2017.
  * [NSW17] Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen.  Dynamic minimum spanning forest with subpolynomial worst-case update time.  In FOCS, 2017.
  * [Ram97] Prakash Ramanan.  Tight $\omega$ (n lg n) lower bound for finding a longest increasing subsequence.  International journal of computer mathematics, 65(3-4):161–164, 1997.
  * [RSSS19] Aviad Runbinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun.  Approximation algorithms for LCS and LIS with truly improved running times.  In FOCS, 2019.
  * [SS10] Michael Saks and C Seshadhri.  Estimating the longest increasing sequence in polylogarithmic time.  In FOCS, 2010.
  * [Tis13] Alexandre Tiskin.  Semi-local string comparison: algorithmic techniques and applications, 2013.  arXiv:0707.3619v21.
  * [Tis15] Alexander Tiskin.  Fast distance multiplication of unit-monge matrices.  Algorithmica, 71(4):859–888, 2015.  doi:10.1007/s00453-013-9830-z.

##  Appendix A Block-based Algorithms [MS20]

We present the block-based framework of Mitzenmacher and Seddighin [MS20] in
this section. They show a reduction that simplifies the problem with respect
to worst-case time constraints. Ultimately, in our algorithms, we prove that
the update time of each operation is bounded in the worst case. However, it is
more convenient to allow for larger update times in some cases, while keeping
a bounded amortized update time.

In the framework of Mitzenmacher and Seddighin [MS20], we start with an array
$a$ of size $n$ and our algorithm is allowed to make a preprocessing of time
$f(n)$. For the next $g(n)$ steps, the processing time of each operation is
bounded by $h(n)$ in the worst case. After $g(n)$ steps, our algorithm is no
longer responsible for the operations and terminates. We refer to such an
algorithm as block-based. Note $f(n)$, $g(n)$, and $h(n)$ are determined based
only on the size $n$ of the initial sequence $a$. We only consider $g(n)\leq
n/2+10$ so that after $g(n)$ operations the size of the sequence remains
asymptotically the same.

We show in the following that a block-based algorithm $\mathcal{A}$ for LIS
with identifiers $\langle f,g,h\rangle$ can be used as a black box to obtain a
dynamic algorithm $\mathcal{A^{\prime}}$ with worst-case update time
$O(\max\\{h(n),f(n)/g(n)\\})$. The approximation factor of the algorithm is
preserved in this reduction.

######  Lemma 36 (proven by Mitzenmacher and Seddighin [MS20]).

Let $\mathcal{A}$ be a block-based algorithm with preprocessing time $f(n)$
that approximates dynamic LIS for up to $g(n)$ many steps with worst-case
update time $h(n)$. If $g(n)\leq n/2+10$ then there exists a dynamic algorithm
$\mathcal{A}^{\prime}$ for the same problem whose worst-case update time is
bounded by $O(\max\\{h(n),f(n)/g(n)\\})$ and whose approximation factor is the
same as $\mathcal{A}$.

$\mathcal{B}_{1}$$a^{(1)}$$\mathcal{B}_{2}$$\mathcal{B}_{3}$$\dotsc$preprocessingupdating
two operations in each
step$g(n_{1})/10$$g(n_{2})/10$$a^{(2)}$$a^{(3)}$$1$$\frac{9g(n_{1})}{10}$$g(n_{1})$$\frac{9g(n_{1})}{10}+g(n_{2})$$\frac{9(g(n_{1})+g(n_{2}))}{10}$
Figure 26: The reduction is shown in this figure.

Figure 26 gives a pictorial depiction of the proof idea for Lemma 36.
Mitzenmacher and Seddighin [MS20] construct an algorithm
$\mathcal{A^{\prime}}$ in the following way: $\mathcal{A}^{\prime}$ uses
algorithm $\mathcal{A}$ repeatedly. To distinguish between multiple instances
of $\mathcal{A}$, we add subscripts; the first time we use algorithm
$\mathcal{A}$ we call it $\mathcal{B}_{1}$. Every $\mathcal{B}_{i}$ is
basically a copy of the block-based algorithm $\mathcal{A}$ which is modified
slightly to execute the preprocessing part in multiple steps. We begin with
using our block-based algorithm $\mathcal{B}_{1}$ at step 1. At this point we
call the initial array (which is empty) $a^{(1)}$. Also, we refer to its size
by $n_{1}$ which is equal to 0. Since the size of the array is constant, so is
the preprocessing time and therefore we can ignore it when bounding the time
complexity. For $g(n_{1})$ many steps, we use algorithm $\mathcal{B}_{1}$ to
preserve an approximate solution and from then on, we use a separate algorithm
for the rest of the operations, namely $\mathcal{B}_{2}$. The construction of
$\mathcal{B}_{2}$ is given below:

When $\mathcal{B}_{1}$ has gone $9/10$ of the way and is only responsible for
$g(n_{1})/10$ more operations, we initiate algorithm $\mathcal{B}_{2}$. Let
$a^{(2)}$ be the array at this point and $n_{2}$ be its size.
$\mathcal{B}_{2}$ needs to run the preprocessing step which requires
$f(n_{2})$ many operations. This may not be possible in a single step,
therefore, we break the computation into $g(n_{1})/20$ pieces and execute each
piece in the next $g(n_{1})/20$ steps. Moreover, in the next $g(n_{1})/20$
steps operations that arrive after the construction of $\mathcal{B}_{2}$ are
processed: two operations in each step. While this is happening, algorithm
$\mathcal{B}_{1}$ processes the operations and updates the solution size.
$g(n_{1})/10$ many steps after the construction of $\mathcal{B}_{2}$,
algorithm $\mathcal{B}_{2}$ has already finished the preprocessing and all the
operations that have arrived so far are applied to it. This is exactly the
time that $\mathcal{B}_{1}$ terminates, and from then on, we use algorithm
$\mathcal{B}_{2}$ to process each operation. Similarly, $\mathcal{B}_{3}$ is
constructed when $\mathcal{B}_{2}$ has applied $g(n_{2})9/10$ operations. This
construction goes on as long as operations arrive.

We emphasize that there is a constant-factor overhead in the update-time of
the reduction which is hidden in the $O$ notation. Moreover, the constant
factor is regardless of algorithm $\mathcal{A}$ and is the same for all
possible algorithms. It follows from the same idea that if we separate the
notion of query from the notion of operation (as we do in Section 4), still
the same reduction gives us a dynamic algorithm from a block-based algorithm.

##  Appendix B The Algorithm of Chen, Chu, and Pinsker [CCP13]

For formal proofs, we refer the reader to [CCP13]. Chen, Chu, and Pinsker
[CCP13] propose the following algorithm to maintain a solution for dynamic
LIS.

For each element $i$ of the array, define $l(i)$ to be the size of the longest
increasing subsequence ending at element $a_{i}$ of the array. Chen, Chu, and
Pinsker [CCP13] refer to this quantity as the level of element $i$. Notice
that $l(i)$ can be computed in time $\widetilde{O}(n)$ for all elements of the
array using the patience sorting algorithm.

Define $L^{\prime}_{k}$ to be the set of elements whose levels are equal to
$k$. The algorithm of Chen, Chu, and Pinsker [CCP13] maintains a balanced
binary tree for each $L^{\prime}_{k}$ that contains the corresponding
elements. One key observation is that for each $k$, all the elements of
$L^{\prime}_{k}$ are decreasing, otherwise their levels would not be the same.

When a new element is added to the array, $L^{\prime}_{k}$’s may change. More
precisely, after an element addition, the levels of some elements may change
(but only by 1). Similarly, element removal may change the levels of the
elements of the array but again the change is bounded by $1$. Chen, Chu, and
Pinsker [CCP13], show that after an insertion, for each $L^{\prime}_{k}$, the
levels of only one interval of the elements may increase. In other words, for
each $L^{\prime}_{k}$, there are two numbers $\alpha$ and $\beta$ such that
all the elements whose values are within $[\alpha,\beta]$ increase their
levels and the rest remain in $L^{\prime}_{k}$.

Thus, they use a special balanced tree structure that allows for interval
deletion and interval addition in logarithmic time. Therefore, all that
remains is to detect which interval of each $L^{\prime}_{k}$ changes after
each operation. They show that this can be computed in time $O(\log n)$ for
all $L^{\prime}_{k}$’s via binary search. Since the number of different levels
is equal to the size of the LIS, their update time depends on the size of the
solution.

$L^{\prime}_{1}\ =\ \langle 1\rangle$$L^{\prime}_{2}\ =\ \langle
5,2\rangle$$L^{\prime}_{3}\ =\ \langle 4\rangle$$\langle 1,\ 5,\ 2,\
\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}3\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\
,\ 4,\ 6,\ 7,\ 9,\ 10,\ 8\rangle$$\langle 1,\ 5,\ 2\ ,\ 4,\ 6,\ 7,\ 9,\ 10,\
8\rangle$$L^{\prime}_{4}\ =\ \langle 6\rangle$$L^{\prime}_{5}\ =\ \langle
7\rangle$$L^{\prime}_{6}\ =\ \langle 9,8\rangle$$L^{\prime}_{7}\ =\ \langle
10\rangle$$3$ Figure 27: This example illustrates how an element addition is
handled in the algorithm of Chen, Chu, and Pinsker [CCP13]. Inserting element
$3$ to the array changes the levels of the elements. Upward arrows show that
the level of the corresponding element increases after we add $3$ to the
array.

When $n$ elements are given, their runtime for constructing the data structure
is $\widetilde{O}(n)$ since patience sorting gives us all the levels in time
$\widetilde{O}(n)$ and the balanced trees can be constructed in time
$\widetilde{O}(n)$ for all $L^{\prime}_{k}$.