2

There is a particular class of algorithm coding problems which require us to evaluate multiple queries which can be of two kind :

  1. Perform search over a range of data
  2. Update the data over a given range

One example which I've been recently working on is this(though not the only one) : Quadrant Queries

Now, to optimize my algorithm, I have had one idea : I can use dynamic programming to keep the search results for a particular range, and generate data for other ranges as required.

For example, if I have to calculate sum of numbers in an array from index 4 to 7, I can already keep sum of elements upto 4 and sum of elements upto 7 which is easy and then I'll just need the difference of the two + 4th element which is O(1). But this raises another problem : During the update operation, I'll have to update my stored search data for all the elements following the updated element. This seems to be inefficient, though I did not try it practically.

Someone suggested me that I can combine subsequent update operations using some special data structure.(Actually read it on some forum).

Question: Is there a known way to optimize these kind of problems? Is there a special data structure that does it? The idea I mentioned;Is it possible that it might be more efficient than direct approach? Should I try it out?

Cheeku
  • 833
  • 1
  • 8
  • 22
  • Look into segment trees and binary indexed trees. – IVlad Aug 31 '13 at 18:37
  • My answer to http://stackoverflow.com/questions/18065238 might help explain the difference between segment trees and binary indexed trees. Briefly, to update a range you want to use segment trees with lazy update. – Peter de Rivaz Aug 31 '13 at 20:25
  • I have used BIT before, so I think it will work in this particular one. But, if the operation is multiplication rather than addition, using BIT is a little hefty. I am gonna check out segment trees. – Cheeku Aug 31 '13 at 23:08

1 Answers1

1

It might help: Segment Trees (Range-Range part)

Community
  • 1
  • 1
Schabowy
  • 121
  • 1
  • 3
  • Okay! Segment Trees seem to work for me! I don't see if it is the most efficient, but definitely more efficient than what I had. – Cheeku Sep 01 '13 at 01:07