2

Let's say I have a binary tree of height h, that have elements of x1, x2, ... xn.

xi element is initially at the ith leftmost leaf. The tree should support the following methods in O(h) time

  1. add(i, j, k) where 1 <= i <= j =< n. This operation adds value k to the values of all leftmost nodes which are between i and j. For example, add(2,5,3) operation increments all leftmost nodes which are between 2th and 5th nodes by 3.

  2. get(i): return the value of ith leftmost leaf.

What should be stored at the internal nodes for that properties?

Note: I am not looking for an exact answer but any hint on how to approach the problem would be great.

user1072739
  • 21
  • 1

1 Answers1

0

As I understand the question, the position of the xi'th element never changes, and the tree isn't a search tree, the search is based solely on the position of the node.

You can store an offset in the non leaves vertices, indicating the value change of its descendant.

add(i,j,k) will start from the root, and deepen in the tree, and increase a node's value by k if and only if, all its descendants are within the range [i,j]. If it had increased the value, no further deepening will occur.
Note1: In a single add() operation, you might need to add more then one number.
Note2: You actually need to add at most O(logn) = O(logh) values [convince yourself why. Hint: binary presentation of number up to n requires O(logn) bits], which later gives you [again, make sure you understand why] the O(logh) needed complexity.

get(i) is then trivial: summarize the values from the root to the i'th leaf, and return this sum.

Since it seems homework, I will not post a pseudo-code, this guidelines should get you started with this assigment.

amit
  • 175,853
  • 27
  • 231
  • 333
  • In the "increase a node's value by k if and only if ..." part are you assuming that nodes are traversed in-order? – James Waldby - jwpat7 Nov 30 '11 at 07:40
  • You are increasing a value of a non leaf node, you can traverse it as you wish, inorder is just one possibility, and in any case, you do not need to traverse on more then `2*h` vertices, and at most 2 leaves. – amit Nov 30 '11 at 07:59
  • Actually, I need to store at most O(1) space for each internal node. I know that Knuth has a clever algorithm to iterate over a binary tree in O(1) auxiliary space with O(nlogn) time: http://stackoverflow.com/questions/791052/iterating-over-a-binary-tree-with-o1-auxiliary-space So I am considering to convert this solution to mine but cannot see how.. Maybe temporarily adding back references from certain leaves somehow can do the trick because add() operation doesn't return anything.. it simply helps me to answer get(i) operations.. – user1072739 Nov 30 '11 at 11:29
  • You need `O(1)` space for each internal node, just the offset value, for each node. Also, you can make sure the algorithm runs with `O(1)` space, if you add an extra 'parent' node to each vertex, and without it, the recursion causes `O(h)` total space, which is on average `O(1)` for node, since `h <= n`. – amit Nov 30 '11 at 11:38
  • amit, you missed the point of my comment. Re "increase a node's value by k if and only if, all its descendants are within the range [i,j]" -- In an in-order traversal, if all descendants of a node are in range, so is the node. In a pre- or post-order traversal, with all of node's descendants in range, the node itself may or may not be in range. – James Waldby - jwpat7 Nov 30 '11 at 15:44
  • The tree is might not be complete or balanced and the data stored in leaves are not in sorted order. Actually i cannot see how we get O(h) time per operation. How can we ensure? – user1072739 Nov 30 '11 at 22:34
  • @user1072739: h > O(logn) => O(h) > O(logn). if the tree is balanced, your complexity is O(logn) = O(h). else, you are still on O(h), since O(logn) < O(logh) – amit Dec 01 '11 at 06:35