Range sum supporting dynamically adding data

Question

I am looking for a data structure that can do range-sums like a Segment tree but can support adding a new piece of data at any time without rebuilding the entire tree. I believe I can hack together a segment which can handle adding new data dynamically but it wouldn't be pretty.

If it helps, I will always be "appending" data since it is time based.

Example:

Order[time=0, quantity=1]
Order[time=1, quantity=2]
Order[time=2, quantity=4]
Order[time=3, quantity=2]

Range sum segment Tree:

                sum[0->3=9]
    sum[0->1=3]             sum[2->3=6]
time0=1     time1=2     time2=4     time3=2

What would happen to the tree above if I added Order[time=4, quantity=3]

                                        sum[0->4=12]
               sum[0->3=9]                                        sum[4->4=3]
    sum[0->1=3]           sum[2->3=6]                  sum[4->4=3]
time0=1     time1=2   time2=4     time3=2          time4=3

I can certainly use the approach above but I am hoping there is something better.

Peter de Rivaz · Accepted Answer · 2013-11-04 20:08:36Z

1

If you are always appending data at consecutive time values, you could consider simply storing the cumulative sum of all the quantities in an array.

Your example of 1,2,4,2 would make the array 1,3,7,9:

1
1+2=3
1+2+4=7
1+2+4+2=9

You can then do a sum of values over a range of elements by subtracting two elements of the cumulative array.

This is O(1) for append and O(1) for a range sum.

answered Nov 4, 2013 at 20:08

Peter de Rivaz

33.6k4 gold badges51 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Justin Over a year ago

Interesting and simple, my example above was a bit simpler then my actual use case. Let me see if I can apply the same idea to my data.

Aaron Dufour Over a year ago

@Justin Updates (as opposed to appends) would be very expensive (O(n)) under this model, but it might be a good fit if you don't expect many of those.

Justin Over a year ago

There will be no updates to previous data; so that is not a concern.

Aaron Dufour Over a year ago

@Justin In that case this will work better for you than Fenwick trees - their advantage is fast updates, and they give up a bit of speed in fetches to do that.

Aaron Dufour · Accepted Answer · 2013-11-04 20:14:44Z

1

I'm not completely sure I understand your problem, but it sounds like you're looking for a Fenwick tree. From an array, a Fenwick tree can be built in nlog(n), they allow summing over a contiguous range in log(n), and you can update a node in log(n). I'm not sure about extending the array; I've never tried that, but I expect it would be log(n) as well.

answered Nov 4, 2013 at 20:14

Aaron Dufour

17.6k1 gold badge51 silver badges73 bronze badges

3 Comments

Justin Over a year ago

Yea, I was looking at a Fenwick tree also but it started looking less appealing when I wanted to "resize" the underlying array. It's still an option.

Aaron Dufour Over a year ago

@Justin If it sounds like it would help, and being able to extend the array by one index in log^2(n) time would be quick enough, I can try to write up the algorithm. I think that would be the worst-case time. If you explain the problem in more detail, I might be able to help more - I'm not terribly familiar with Segment trees.

Justin Over a year ago

I'd be interested in seeing the algorithm, if you get the time to write it up.

Collectives™ on Stack Overflow

Range sum supporting dynamically adding data

2 Answers 2

4 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related