World's most popular travel blog for travel bloggers.

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

, , No Comments
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:

We start with a 3x3 array of all 0s.

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 updates...

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.

Asked By : user150878
Answered By : aelguindy

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65289

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback