2D range multiplication data structure

Правка en2, от ceciver, 2025-02-12 20:37:24

I'm working on an optimization problem and I came across the following subproblem:

Given an $$$ n \times n $$$ matrix, perform the following queries:

$$$1)$$$ Multiply all elements in a sub-matrix by $$$x$$$ in $$$O(log^2n)$$$.

$$$2)$$$ Get the sum of elements in a sub-matrix in $$$O(log^2n)$$$.

I know how to solve this problem in 1D using lazy propagation and segment tree, but I couldn't find a way to extend it to 2D or more. Is it even possible? I'm interested in logarithmic solutions per query, but if there's anything better than $$$O(n)$$$, I would like to hear about it as well.

Теги data structures, segment tree, lazy propagation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ceciver 2025-02-12 20:37:24 28
en1 Английский ceciver 2025-02-12 20:31:59 623 Initial revision (published)