Faster Dynamic Range Mode

The algorithm uses the idea by Alon, Galil and Margalit in [1], which computes the Min-Plus product of $A,B$ in $\tilde{O}(Wn^{\omega(s)})$ time.

In their algorithm, they first construct matrix $A^{\prime}$ defined by

We can define $B^{\prime}$ similarly. Then the product $A^{\prime}B^{\prime}$ captures some useful information about the Min-Plus product of $A$ and $B$. Namely, for each entry $(A^{\prime}B^{\prime})_{i,j}$, we can uniquely write it as $\sum_{t\geq 0}r^{i,j}_{t}(n^{s}+1)^{t}$ for integers $0\leq r^{i,j}_{t}\leq n^{s}$. Note that $r^{i,j}_{t}$ exactly equals the number of $k$ such that $A_{i,k}+B_{k,j}=t-2W$. Thus, we can use $A^{\prime}B^{\prime}$ to compute the Min-Plus Product of $A$ and $B$.

In our algorithm, we use a range tree to maintain the sequence $r^{i,j}_{t}$ for each pair of $i,j$. The preprocessing takes $\tilde{O}(Wn^{\omega(s)})$ time, which is the time to compute $A^{\prime}B^{\prime}$ and the sequences $r^{i,j}_{t}$.

During each query, we are given $i,j,S$. We enumerate each $k\in S$, and decrement $r^{i,j}_{A_{i,k}+B_{k,j}+2W}$ in the range tree if $A_{i,j}+B_{k,j}<\infty$. After we do this for every $k\in S$, we query the range tree for the smallest $t$ such that $r^{i,j}_{t}\neq 0$, so $t-2W$ is the answer to the Min-Plus-Query query. After each query, we need to restore the values of $r^{i,j}$, which can also be done efficiently. The query time is $\tilde{O}(|S|)$, since each update and each query of range tree takes $\tilde{O}(1)$ time. The space complexity should be clear from the algorithm.

For simplicity, assume $P$ is a factor of $n^{s}$. We sort each column of matrix $B$ and put entries whose rank is between $(\ell-1)P+1$ and $\ell P$ into the $\ell$-th bucket. We use $K_{j,\ell}$ to denote the set of row indices of entries in the $\ell$-th bucket of the column $j$. We use $L_{j,\ell}$ to denote the smallest entry value of the bucket $K_{j,\ell}$, and use $H_{j,\ell}$ to denote the largest entry value. Formally,

For each $\ell\in[n^{s}/P]$, we do the following²²2We use $[n]$, with $n$ integer, to denote the set $\{1,2,\ldots,n\}$.. We create an $n^{s}\times n$ matrix $B^{\ell}$ and initialize all its entries to $\infty$. Then for each column $j$, if $H_{j,\ell}-L_{j,\ell}\leq 2W$ (we will call it a small bucket), we set $B^{\ell}_{k,j}:=B_{k,j}-L_{j,\ell}-W$ for all $k\in K_{j,\ell}$. We will handle the case $H_{j,\ell}-L_{j,\ell}>2W$ (large bucket) later. Clearly, all entries in $B^{\ell}$ have values in $\{-W,\ldots,W\}\cup\{\infty\}$, so we can use the algorithm in Lemma 4.2 to preprocess $A$ and $B^{\ell}$ and store the data structure in $D^{\ell}$. Also, for each pair $(i,j)$, we create a range tree $\mathcal{T}_{\text{small}}^{i,j}$ on the sequence $(A\star B^{1})_{i,j},(A\star B^{2})_{i,j},(A\star B^{3})_{i,j},\ldots$, $(A\star B^{n^{s}/P})_{i,j}$, which stores the optimal Min-Plus values when $k$ is from a specific small bucket. This part takes $\tilde{O}(\frac{n^{s}}{P}Wn^{\omega(s)})$ time. The space complexity is $\frac{n^{s}}{P}$ times more than the space complexity of Lemma 4.2, so space complexity of this part is $\tilde{O}(\frac{Wn^{2+s}}{P}+\frac{n^{1+2s}}{P})$.

We also do the following preprocessing for buckets where $H_{j,\ell}-L_{j,\ell}>2W$. We first create a $0/1$ matrix $\bar{A}$ where $\bar{A}_{i,k}=1$ if and only if $A_{i,k}\neq\infty$. Then for each $\ell\in[n^{s}/P]$, we create a $0/1$ matrix $\bar{B}^{\ell}$ such that $\bar{B}^{\ell}_{k,j}=1$ if and only if $k\in K_{j,\ell}$ and $H_{j,\ell}-L_{j,\ell}>2W$. Then we use fast matrix multiplication to compute the product $\bar{A}\bar{B}^{\ell}$. If $K_{j,\ell}$ is a large bucket, the $(i,j)$-th entry of $\bar{A}\bar{B}^{\ell}$ is the number of $k\in K_{j,\ell}$ such that $A_{i,k}<\infty$; if $K_{j,\ell}$ is a small bucket, the $(i,j)$-th entry is $0$. For each pair $(i,j)$, we create a range tree $\mathcal{T}_{\text{large}}^{i,j}$ on the sequence $(\bar{A}\bar{B}^{1})_{i,j},(\bar{A}\bar{B}^{2})_{i,j},(\bar{A}\bar{B}^{3})_{i,j},\ldots,(\bar{A}\bar{B}^{n^{s}/P})_{i,j}$. This part takes $\tilde{O}(\frac{n^{s}}{P}n^{\omega(s)})$ time, which is dominated by the time for small buckets. The space complexity is also dominated by the data structures for small buckets.

Now we describe how to handle a query $(i,j,S)$. First consider small buckets. In $O(|S|)$ time, we can compute the set of small buckets $K_{j,\ell}$ that intersect with $S$. For each such $K_{j,\ell}$, we can query the data structure $D^{\ell}$ with input $(i,j,S\cap K_{j,\ell})$ to get the optimum value when $k\in K_{j,\ell}$. For each small bucket that intersects with $S$, we can set its corresponding value in the range tree $\mathcal{T}_{\text{small}}^{i,j}$ to $\infty$, then we can compute the optimum value of all small buckets that do not intersect with $S$ by querying the minimum value of the range tree $\mathcal{T}_{\text{small}}^{i,j}$. After this query, we need to restore all values in the range tree. It takes $\tilde{O}(|S|)$ time to handle small buckets on query.

Now consider large buckets. Intuitively, we want to enumerate indices in all large buckets $K_{j,\ell}$ such that there exists an index $k\in K_{j,\ell}\cap([n^{s}]\setminus S)$ where $A_{i,k}<\infty$. However, doing so would be prohibitively expensive. We will show that we only need two such buckets. Consider three large buckets $l_{1}<l_{2}<l_{3}$. Pick any $k_{1}\in T_{j,l_{1}},k_{3}\in T_{j,l_{3}}$ such that $A_{i,k_{1}}<\infty$. Since

$k_{3}$ can never be the optimum. Thus, it suffices to find the smallest two buckets such that there exists an index $k\in K_{j,\ell}\cap([n^{s}]\setminus S)$ where $A_{i,k}<\infty$, and then enumerate all indices in these two buckets. To find such two buckets, we can enumerate over all indices $k\in S$, and if $A_{i,k}<\infty$ we can decrement the corresponding value in the range tree $\mathcal{T}_{\text{large}}^{i,j}$. Thus, we can compute the two smallest buckets by querying the two earliest nonzero values in the range tree. We also need to restore the range tree after the query. The range tree part takes $\tilde{O}(|S|)$ time and scanning the two large buckets requires $O(P)$ time. Thus, this step takes $\tilde{O}(|S|+P)$ time.

At this point, we will know the bucket that contains the optimum index $k^{*}$. Thus, we can iterate all indices in this bucket to actually get the witness for the Min-Plus-Query-Witness query. It takes $O(P)$ time to do so.

In summary, the preprocessing time, query time, and space complexity meet the promise in the lemma statement.

Preprocessing Step 1: Create an Estimation Matrix

First, we create a matrix $\hat{B}$, where $\hat{B}_{k,j}=B_{k,\lceil j/\Delta\rceil\Delta}$. By the property of matrix $B$, $|\hat{B}_{k,j}-B_{k,j}|\leq W$ for every $k,j$. For each pair $(i,j)$, we compute the $L$-th smallest value of $A_{i,k}+\hat{B}_{k,j}$ among all $1\leq k\leq n^{s}$, and denote this value by $\hat{C}^{L}_{i,j}$. Notice that $\hat{C}^{L}_{i,j}=\hat{C}^{L}_{i,\lceil j/\Delta\rceil\Delta}$, so it suffices to compute $\hat{C}^{L}_{i,j}$ when $j$ is a multiple of $\Delta$, and we can infer other values correctly. It takes $O(n^{s})$ time to compute each $\hat{C}^{L}_{i,j}$, so this step takes $O(n^{2+s}/\Delta)$ time.

If we similarly define $C^{L}_{i,j}$ as the $L$-th smallest value of $A_{i,k}+B_{k,j}$ among all $1\leq k\leq n^{s}$, then $|C^{L}_{i,j}-\hat{C}^{L}_{i,j}|\leq W$ by the following claim, whose proof is omitted for space constraint.

Given two sequences $(a_{k})_{k=1}^{m}$ and $(b_{k})_{k=1}^{m}$ such that $|a_{k}-b_{k}|\leq W$, then the $L$-th smallest element of $a$ and the the $L$-th smallest element of $b$ differ by at most $W$.

Also, in $\tilde{O}(n^{2+s}/\Delta)$ time, we can compute a sorted list $\mathcal{L}^{i,j}_{\text{small}}$ of indices $k$ sorted by the value $A_{i,k}+\hat{B}_{k,j}-\hat{C}^{L}_{k,j}$, for every $i$, and every $j$ that is a multiple of $\Delta$.

The space complexity in this step is not dominating.

For some integer $\rho\geq 1$, we will perform $\rho$ rounds of the following algorithm. At the $r$-th round for some $1\leq r\leq\rho$, we randomly sample $j^{r}\in[n]$, and let $A^{r}_{i,k}:=A_{i,k}+B_{k,j^{r}}-\hat{C}^{L}_{i,j^{r}}$ and $B^{r}_{k,j}:=B_{k,j}-B_{k,j^{r}}$. Clearly, $A^{r}_{i,k}+B^{r}_{k,j}=A_{i,k}+B_{k,j}-\hat{C}^{L}_{i,j^{r}}$. For each pair $(i,k)$, we find the smallest $r$ such that $|A^{r}_{i,k}|\leq 3W$. We keep these entries as they are and replace all other entries by $\infty$. For every $(i,k)$, there exists at most one $r$ such that $A^{r}_{i,k}\neq\infty$. Then we use Lemma 4.4 to preprocess $A^{r}$ and $B^{r}$ for every $1\leq r\leq\rho$. Thus, this part takes $O(\rho\frac{n^{s}}{P}Wn^{\omega(s)})$ time, for some integer $P$ to be determined later. Note that this parameter also affects the query time. This step stores $\rho$ copies of the data structure from Lemma 4.4, so the space complexity is $\tilde{O}(\rho\frac{Wn^{2+s}}{P}+\rho\frac{n^{1+2s}}{P})$.

Note that this step is the only step that uses randomization. We can use the method of [26], Appendix A, to derandomize it. We omit the details for simplicity.

For a pair $(i,k)$, if $A^{r}_{i,k}\neq\infty$ for any $r$, we call $(i,k)$ covered; otherwise, we call the pair $(i,k)$ uncovered. For each pair $(i,j)$, we enumerate all $k$ such that $|A_{i,k}+\hat{B}_{k,j}-\hat{C}^{L}_{i,j}|\leq 2W$ and $(i,k)$ is uncovered. Notice that since $A_{i,k}+\hat{B}_{k,j}-\hat{C}^{L}_{i,j}=A_{i,k}+\hat{B}_{k,\lceil j/\Delta\rceil\Delta}-\hat{C}^{L}_{i,\lceil j/\Delta\rceil\Delta}$, we only need to exhaustively enumerate all $k\in[n^{s}]$ when $j$ is a multiple of $\Delta$. Thus, if the total number of $(i,k,j)$ where $|A_{i,k}+\hat{B}_{k,j}-\hat{C}^{L}_{i,j}|\leq 2W$ and $(i,k)$ is uncovered is $X$, then we can enumerate all such triples $(i,k,j)$ in $O(X+n^{2+s}/\Delta)$ time.

It remains to bound the total number of triples that satisfy the condition. Fix an arbitrary pair $(i,k)$, and suppose the number of $j$ such that $|A_{i,k}+\hat{B}_{k,j}-\hat{C}^{L}_{i,j}|\leq 2W$ is at least $(10+s)n\ln n/\rho$. Then with probability at least $1-(1-\frac{(10+s)\ln n}{\rho})^{\rho}\geq 1-\frac{1}{n^{10+s}}$, we pick a $j^{r}$ where $|A_{i,k}+\hat{B}_{k,j^{r}}-\hat{C}^{L}_{i,j^{r}}|\leq 2W$. Therefore,

which means $(i,k)$ is covered. Therefore, with high probability, all pairs of $(i,k)$ where the number of $j$ such that $|A_{i,k}+\hat{B}_{k,j}-\hat{C}^{L}_{i,j}|\leq 2W$ is at least $(10+s)n\ln n/\rho$ will be covered. In other words, $X=O(n^{1+s}\cdot n\ln n/\rho)=\tilde{O}(n^{2+s}/\rho)$.

For each pair $(i,j)$, if we enumerate more than $L$ indices $k$, we only keep the $L$ values of $k$ that give the smallest values of $A_{i,k}+B_{k,j}$. We call this list $\mathcal{L}^{i,j}_{\text{triple}}$. From previous discussion, the time cost in this step is $\tilde{O}(n^{2+s}/\rho+n^{2+s}/\Delta)$. Since we need to store all the triples, the space complexity is $O(n^{2+s}/\rho)$.

Now we discuss how to handle queries. For each query $(S,i,j)$, let $k^{*}=\operatorname*{arg\,min}_{k\not\in S}A_{i,k}+B_{k,j}$ be the optimum index. Consider two cases:

• •

  $(i,k^{*})$ is covered. By definition of being covered, there exists a round $r$ such that $A^{r}_{i,k^{*}}=A_{i,k^{*}}+B_{k^{*},j^{r}}-\hat{C}^{L}_{i,j^{r}}$, so $A^{r}_{i,k^{*}}+B^{r}_{k^{*},j}=A_{i,k^{*}}+B_{k^{*},j}-\hat{C}^{L}_{i,j^{r}}$. Therefore, we can query the data structure in Lemma 4.4 for every $A^{r}$ and $B^{r}$ and denote $b^{r}$ as the result. The answer is given by the smallest value of $b^{r}+\hat{C}^{L}_{i,j^{r}}$ over all $r$. The witness is given by the data structure of Lemma 4.4.

  Note that when querying $A^{r}$ and $B^{r}$, we only need to pass the set $\{k\in S:A^{r}_{i,k}\neq\infty\}$. For every $k\in S$, there is at most one $r$ such that $A^{r}_{i,k}\neq\infty$, so the total size of the sets passing to the data structure of Lemma 4.4 is $|S|$. Thus, this case takes $O(|S|+\rho P)$ time.

• •

  $(i,k^{*})$ is uncovered. There are still two possibilities to consider in this case.

  • –

    Possibility I: $A_{i,k^{*}}+\hat{B}_{k^{*},j}-\hat{C}^{L}_{i,j}<-2W$. In this case,

    $$A_{i,k^{*}}+B_{k^{*},j}\leq A_{i,k^{*}}+\hat{B}_{k^{*},j}+W<\hat{C}^{L}_{i,j}-W,$$

    so the optimum value is smaller than $\hat{C}^{L}_{i,j}$. By reading the list $\mathcal{L}^{i,\lceil j/\Delta\rceil\Delta}_{\text{small}}$, we can effectively find all such $k$ where $A_{i,k}+\hat{B}_{k,j}-\hat{C}^{L}_{i,j}<-2W$ in time linear to the number of such $k$. The number of such $k$ is at most $L$, by the definition of $\hat{C}^{L}_{i,j}$. Thus, this part takes $O(L)$ time.

  • –

    Possibility II: $A_{i,k^{*}}+\hat{B}_{k^{*},j}-\hat{C}^{L}_{i,j}\geq-2W$. In fact, in this case, we further have

    $$A_{i,k^{*}}+\hat{B}_{k^{*},j}-\hat{C}^{L}_{i,j}\leq A_{i,k^{*}}+B_{k^{*},j}-C^{L}_{i,j}+2W\leq 2W,$$

    where $A_{i,k^{*}}+B_{k^{*},j}-C^{L}_{i,j}\leq 0$ because $|S|<L$. Therefore, in this case, we have $|A_{i,k^{*}}+\hat{B}_{k^{*},j}-\hat{C}^{L}_{i,j}|\leq 2W$, so we can enumerate all indices in $\mathcal{L}^{i,j}_{\text{triple}}$ and take the best choice. This takes $O(L)$ time.

In summary, the preprocessing time is

and the query time is $\tilde{O}(L+\rho P)$. To balance the terms, we can set $\rho=\Delta$ and $P=\frac{L}{\Delta}$ to achieve a $\tilde{O}(\Delta^{2}\frac{n^{s}}{L}Wn^{\omega(s)}+\frac{n^{2+s}}{\Delta})$ preprocess time and a $\tilde{O}(L)$ query time. Note that since we need $P\geq 1$, we must have $L=\Omega(\Delta)$.

From the preprocessing steps, the space complexity is $\tilde{O}(\rho\frac{Wn^{2+s}}{P}+\rho\frac{n^{1+2s}}{P}+n^{2+s}/\rho)$. Plugging in $\rho=\Delta$ and $P=\frac{L}{\Delta}$ reduces this to

as given in the statement of the lemma.

Let $\Delta,W\geq 1$ be small polynomials in $n$ to be fixed later. Define $I(j)$ to be the interval $[j-\Delta+1,j]$.

Let $j^{\prime}$ be any multiple of $\Delta$. By property 2 of matrix $B$, $\sum_{k=1}^{n^{s}}B_{k,j}-\sum_{k=1}^{n^{s}}B_{k,j+1}\leq n^{s}$ for any $j\in I(j^{\prime})$. Thus, we have

By averaging, there are at most $\Delta n^{s}/W$ indices $k\in[n^{s}]$ such that $B_{k,j^{\prime}-\Delta+1}-B_{k,j^{\prime}}>W$. We create a new matrix $\hat{B}$, initially the same as matrix $B$. For each $k$ such that $B_{k,j^{\prime}-\Delta+1}-B_{k,j^{\prime}}>W$, and for each $j\in I(j^{\prime})$, we set $\hat{B}_{k,j}$ as $M$, where $M$ is some large enough integer. After this replacement, $\hat{B}_{k,j^{\prime}-\Delta+1}-\hat{B}_{k,j^{\prime}}\leq W$ for any $k$ and any $j^{\prime}$ multiple of $\Delta$. Also, since $\hat{B}_{k,j^{\prime}-\Delta+1}\geq\hat{B}_{k,j}\geq\hat{B}_{k,j^{\prime}}$ for any $j\in I(j^{\prime})$, we have that $|\hat{B}_{k,j_{1}}-\hat{B}_{k,j_{2}}|\leq W$ as long as $\lceil j_{1}/\Delta\rceil=\lceil j_{2}/\Delta\rceil$. Therefore, we can use Lemma 4.6 to preprocess $A$ and $\hat{B}$ in $O(\Delta^{2}\frac{n^{s}}{L}Wn^{\omega(s)}+\frac{n^{2+s}}{\Delta})$ time. The space complexity is $\tilde{O}(\frac{\Delta^{2}Wn^{2+s}}{L}+\frac{\Delta^{2}n^{1+2s}}{L}+\frac{n^{2+s}}{\Delta})$.