On Updating and Querying Submatrices

Jason Yang, Jun Wan

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…