Here's a question, is it possible to implement a data structures that supports these operations online:
- 2d Range update(only the add operation, no negative number for adding)
- 2d Range queries(get the sum)
- use Low memory(possibly $$$O(nlogn)$$$)
Here are the constraints:
- $$$n \leq 10^5$$$
- $$$q \leq 10^5$$$
I think a fenwick tree could work but I'm not sure if it will TLE or not.
If anyone could verify that using a fenwick tree could work please let me know. Thanks in advance!
You can check out this source. O(N log N) memory is possible, but only with offline updates.
It has to be online updates, there are things I forgot to mention, there are $$$q$$$ queries which have 2 types:
Still doable in $$$O(q)$$$ memory.
Yes, it is possible. You can do it even in $$$O(q)$$$ memory btw.