3

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?

Improve this question
1
  • I have created a segment tree for a[n] where the root contain [i,j] , if i<j then we fill left child with [i,(i+j)/2] and right child with [(i=j)/2 +1,j] .So atlast we get all leafs as array element and we can access array element in O(logn)time. Commented Aug 6, 2011 at 17:44

2 Answers 2

Reset to default
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!

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

Comments

0

a tree solution:

create a full tree, whose leaves are your entrees: 1,2,...,n
node.value = inserted value [if node is a leaf]
node.value = node.left.value + node.right.value [if node is not a leaf]

so, actually - for each subtree, its root's value is the sum of the values of all its nodes.

updating an entree is O(logn) since you need to update sums all the way up to the root.

for sum(i,j) we will find the sum of all elements left to i, and all elements right to j, and subtract it from root.value, and we'll get what we needed. so:

 sum(root,i,j) = root.value - sumLeft(i,root) - sumRight(j,root)

the calculation of sumLeft() and sumRight() is simple, [for sumLeft:] just start from the root down to the lower bound, and every time you go left, subtract the right son value, and by doing so, you cut from sum the not needed nodes. [convince yourself why this is true]. at the end, the sum has only the relevat nodes. [same principle for sumRight, but we subtract left sons instead].
pseudo code:

sumLeft(x,root):
  curr <- root
  sum <- root.value
  while (curr is not a leaf):
      if (x is in curr.right):
         curr <- curr.right
      else:
         sum <- sum - curr.right.value
         curr <- curr.left
  return sum
sumRight(x,root):
  curr <- root
  sum <- root.value
  while (curr is not a leaf):
      if (x is in curr.left):
         curr <- curr.left
      else:
         sum <- sum - curr.left.value
         curr <- curr.right
  return sum

so, sum(root,i,j) requires you twice to go down the tree, which is still O(logn), as needed.

EDIT1 :

this is how you add x to entree i, on root: [the question indicates there the oporation is adding to the entree and not replacing it, so this is what this solution assumes. it can be easily modified to insertion as well].

add(root,i,x):
  root.value <- root.value + x
  if root is leaf:
      return
  else if i is in root.left:
     add(root.left,i,x)
  else:
     add(root.right,i,x)

note that you can know exactly which subtree (left or right) of the root, the entree i belongs to [if i < n/2 to the left, else to the right]. explain yourself how it is done for any subtree, and not only the root.

EDIT 2:
example for tree with 8 elements:

                21
      10                 11
  4        6        7        4
1  3     2  4     6   1    2   2

summarize example:

sum(4,6) should provide 4 + 6 + 1 = 11.
sumLeft(4) should provide 1 + 3 + 2 = 6 and it provides: sumLeft(4) = 21 - 11 - 4 = 6 as expected.
sumRight(6) should provide 2 + 2 = 4 and it provides sumLeft(6) = 21 - 11 - 7 =4. [as expected]
so, at overall: sum(4,6) = 21 - 6 - 4 = 11 as expected.

add example:
add(2,4) [adding 4 to the 2nd element] will result in modifying the tree to:

                25
      14                 11
  8        6        7        4
1  7     2  4     6   1    2   2
Improve this answer

4 Comments

can you please tell me how to insert element pls give an exampple taking 10 elements.
@rohit: I editted the answer explaining how to add values to entrees. note I cannot give example with 10 elements since the question clearly indicates n is a power of 2, and 10 is not. I'll be able to supply an example tree with 8 elements later.
you have given an excellent solution Hat off to you But I think in your [code]leftsum(x,root)[/code] and rightsum(x,root) if i write left(x-1,root) right(x+1,root) [keep in mind that if x-1<0 then dont take left sum similarly if x+1>n then dont calculate rightsum and take it as zero ] then your psudo code work perfectly. Correct me If I am Worong.
@rohit: it's a pseusocode, I didn't debug it to see all edge cases. but what you have mentioned seems correct... I gave you only the general guideline, making it a full homework solution requires diving into the edge cases as well. good luck!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.