0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, HackerRank has an increasing number of these types of questions. I was trying to use memoization and failing spectacularly. I'll edit my original question to say it is from HackerRank. $\endgroup$ – user150878 Oct 30 '16 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.