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 subrectangle by $$$x$$$ in $$$O(log^2n)$$$.
$$$2)$$$ Get the sum of elements in a subrectangle 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.