English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we study the $d$-dimensional update-query problem. We providelower bounds on update and query running times, assuming a long-standingconjecture on min-plus matrix multiplication, as well as algorithms that areclose to the lower bounds. Given a $d$-dimensional matrix, an \textit{update}changes each element in a given submatrix from $x$ to $x\bigtriangledown v$,where $v$ is a given constant. A \textit{query} returns the $\bigtriangleup$ ofall elements in a given submatrix. We study the cases where $\bigtriangledown$and $\bigtriangleup$ are both commutative and associative binary operators.When $d = 1$, updates and queries can be performed in $O(\log N)$ worst-casetime for many $(\bigtriangledown,\bigtriangleup)$ by using a segment tree withlazy propagation. However, when $d\ge 2$, similar techniques usually cannot begeneralized. We show that if min-plus matrix multiplication cannot be computedin $O(N^{3-\varepsilon})$ time for any $\varepsilon>0$ (which is widelybelieved to be the case), then for$(\bigtriangledown,\bigtriangleup)=(+,\min)$, either updates or queries cannotboth run in $O(N^{1-\varepsilon})$ time for any constant $\varepsilon>0$, orpreprocessing cannot run in polynomial time. Finally, we show a special casewhere lazy propagation can be generalized for $d\ge 2$ and where updates andqueries can run in $O(\log^d N)$ worst-case time. We present an algorithm thatmeets this running time and is simpler than similar algorithms of previousworks.

On Updating and Querying Submatrices