ceciver's blog

By ceciver, history, 4 days ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it