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
Do you know how to do it in $$$O(n)$$$ per query? Segtree for every row would be $$$O(n \log n)$$$.
No, I don't know to achieve $$$O(n)$$$ per query in general case, but I mentioned it because in my case, I only need to perform updates or sum queries on a single row or a single column in each query (more precisely I need to do the update query on an entire column and the sum query on an entire row) , which can be done naively in $$$O(n)$$$. For $$$O(n)$$$ I've read that quadtree can achieve this, I'm not sure tho?