Complete binary tree as an efficient data-structure

Question

You are given an array of size n(n being a power of two). All the entries of the array are initialized to zero. You have to perform a sequence of the following online operations :

1. Add(i,x) which adds x to the entry A[i].
2. Report sum(i,j) = sum of the entries in the array from indices i to j for any 0 < i < j <= n.

It can be seen easily that we can perform the first operation in O(1) time whereas the second operation may cost O(n) in worst case. Your objective is to perform these operations efficiently. Give a data-structure which will guarantee O(log n) time per operation

I think the solution is segment tree but did know whether i am wrong or right?

Answer 1

Well, you can do this with a tree or you can do it with a more efficient data structure. In either case, you don't need a segment tree -- those are more search-oriented and less data oriented.

For reasons of efficiency, I'd go with an array of arrays where the first array is n sized, the next array is n/2 sized, n/4, n/8, ... 1. Whenever you add x to A[i] (the first array), you also add it to index (i >> 1) (a.k.a. i/2) in the second array, index (i >> 2) (a.k.a. i/4) in the third array, etc...

The trick is in calculating sum(i, j). We're now going to compute both sum(0, j) and sum(0, i - 1) because sum(i, j) = sum(0, j) - sum(0, i - 1).

To compute sum(0, v) (for some v) all you have to do is add up at most a single entry from each level. The pseudocode to sum from 0 to index *not including the index itself is as follows:

sum from 0 to index:
begin
    i = 0
    sum = 0
    while i < maxlevel
        if ((index >> i) & 1) != 0
            sum = sum + array[i][index]
    return sum
end

To get an intuition for why this works, think about the lowest level array and summing from 0 to an even index vs. an odd index. If you're using an even index, you could just do it more efficiently by using the array just above it since it already has every two entries summed already! Effectively, for an odd number index you could just do the same thing as you'd do for an even index, but add the one entry that's the "odd man out" by hand. But since you're going to be summing indices at the second level, you could just do all but potentially the last one (if the new index to sum to) is odd.. Etc, etc, etc.. That's precisely what we're doing here.

Those should be all the pieces you need. If you want to do it with a binary tree, you still can in much the same fashion. You can keep a sum in each node of the binary tree. As you traverse to add a sum to a specific node, also add it to all the nodes you traverse. Likewise, you can use the same trick of finding the zero to index trick. Finding the sum from zero to index now becomes a binary tree traversal where for every node you traverse you add the node's sum and subtract any "right hand" (or higher value) child you are not traversing.

Hopefully I haven't spoiled the homework problem, and by reading this you have enough flavor to get it done but not so much that the problem is now trivialized to mere implementation.

Best of luck!