On Updating and Querying Submatrices

Abstract

In this paper, we study the $d$-dimensional update-query problem. We provide lower bounds on update and query running times, assuming a long-standing conjecture on min-plus matrix multiplication, as well as algorithms that are close to the lower bounds. Given a $d$-dimensional matrix, an \textit{update} changes each element in a given submatrix from $x$ to $x▽v$, where $v$ is a given constant. A \textit{query} returns the $△$ of all elements in a given submatrix. We study the cases where $▽$ and $△$ are both commutative and associative binary operators. When $d=1$, updates and queries can be performed in $O(\log N)$ worst-case time for many $(▽,△)$ by using a segment tree with lazy propagation. However, when $d\ge 2$, similar techniques usually cannot be generalized. We show that if min-plus matrix multiplication cannot be computed in $O(N^{3-\epsilon })$ time for any $\epsilon >0$ (which is widely believed to be the case), then for $(▽,△)=(+,\min )$, either updates or queries cannot both run in $O(N^{1-\epsilon })$ time for any constant $\epsilon >0$, or preprocessing cannot run in polynomial time. Finally, we show a special case where lazy propagation can be generalized for $d\ge 2$ and where updates and queries can run in $O({\log }^{d}N)$ worst-case time. We present an algorithm that meets this running time and is simpler than similar algorithms of previous works.