Блог пользователя ceciver

Автор ceciver, история, 15 месяцев назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится