2020/10/25 by Jason Yang, Jun Wan, Yang, Jason +1
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2010.13180
openalex publication_date 2020/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 update changes each element in a given submatrix from x to x\bigtriangledown v, where v is a given constant. A query returns the \bigtriangleup of all 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-case time for many (\bigtriangledown,\bigtriangleup) by using a segment tree with lazy propagation. However, when d≥ 2, similar techniques usually cannot be generalized. We show that if min-plus matrix multiplication cannot be computed in O(N3-ε) time for any ε>0 (which is widely believed to be the case), then for (\bigtriangledown,\bigtriangleup)=(+,min), either updates or queries cannot both run in O(N1-ε) time for any constant ε>0, or preprocessing cannot run in polynomial time. Finally, we show a special case where lazy propagation can be generalized for d≥ 2 and where updates and queries can run in O(logd N) worst-case time. We present an algorithm that meets this running time and is simpler than similar algorithms of previous works.