World's most popular travel blog for travel bloggers.

# Is there an algorithm or shortcut for continually updating and summing sub-sections of arrays?

, ,
Problem Detail:

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:

Operations:

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)

more queries...

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.

The data structures you're looking for are quad trees (for linear time queries, logarithmic time updates, quadratic space) or the more complicated 2d interval trees (for logarithmic time queries, logarithmic time updates, $O(N^2 \log N)$ space).

I suspect you are trying to solve competitive programming problem, if so please state it in your question.