Let's say I have an NxN array if integers. I want to continually update it, but also continually query for the sum of an arbitrary sub-section. So example would be as follows:
We start with a 3x3 array of all 0s.
update 1,1 to 3
update 1,2 to 1
update 0,0 to 2
update 2,2 to 6
print sub-section starting at 1,1 going to 2,2 (should print 10)
The array looks like this at the time of first query:
2 0 0 0 3 0 0 1 6
I want to do this for much larger arrays, and much more queries in a reasonable amount of time. I believe less than O(N^2) per query is possible. Any ideas?
EDIT: I'm asking this because Hackerrank has several of these types of questions and I was banging my head against a wall trying to come up with a strategy.