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.
ceciver can you plz give the link to the problem ?
It's not a problem on any online judge (as I know), just something on a bigger research project that I'm working on, and I need this kind of optimization.
oh i see