H3X's blog

How to use a binary search tree to compute a range sum
By H3X, 12 years ago, In English

Suppose you have two operations : 1 ADD L R x, add from L to R value x 2 SUM L R, get the sum from L to R.

How can you implement these using any typical BST like treap or splay tree?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

why do you want to use exactly BST ? there are better data structures, segment tree will work as well

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

BST's are mostly used to store a sorted collection of values and be able to efficiently answer queries of the form "What is the element at index 'k'?" or "How many elements bigger/smaller than 'n' are there?", etc.. If you're gonna use range queries, segment trees or BIT's are the way to go. Much easier to code too, btw.

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

Seems that your question is similar to this problem SPOJ HORRIBLE

I am not so sure about BST, but with BIT and Segment Trees should be easier to implement.

The following code shows a BIT implementation topcoder forum.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cause, i know segment tree and bit, i want to do it with bst.

http://www.codeforces.com/contest/284/submission/3345224

see this for example, i can't understand how he does it, but he uses treap to compute the sum from 1 to k.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    here is my code for the problem problem

    I used segment tree. code link : code

    hope it helps :).

    → Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

Consider a BST with the following satellite data in its nodes:

  • num = the number stored in the node
  • sum = Sum of all elements in the subtree
  • size = Amount of nodes in the subtree

And also a function getSum(int l, int r, int a, int b, node *t) that returns the sum of all elements from indexes l to r ([a,b] is the range of indexes in the sub-tree rooted at the current node t). You'd call getSum(l, r, 0, size_of_tree, root), and the code for the function would be something like this...

int getSum(int l, int r, int a, int b, node *t)
{
    // If we're at a node that does not exist or the range in this sub-tree
    // is outside the range we're interested, return 0
    if(t == NULL || a > r || b < l)
        return 0;
        
    // If the range contained in this sub-tree is completely inside the range
    // we're looking for, return the sum of all the nodes in this sub-tree
    if(a >= l  && b <= r)
        return t->sum;

    int left_a = a; // Index of smallest element in left sub-tree
    int left_b = a + l_size - 1; // Index of greatest element in left sub-tree
    int this_node = left_b + 1; // Index of this node
    int right_a = this_node + 1; // Index of smallest element in right sub-tree
    int right_b = b; // Index of greatest element in right sub-tree
    
    // We iterate in its children and, if the current node is inside the range
    // we're looking for, we add it to the sum
    
    int add = (this_node >= l && this_node <= r) ? t->num : 0;

    return getSum(l, r, left_a, left_b, t->left) + add + getSum(l, r, right_a, right_b, t->right);
}
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Awesome! Thank you very much.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

You can also implement SPLIT and MERGE in the BST. You then split the tree twice to isolate the nodes in the range [l, r]. Keep in mind SPLIT takes log n time (assuming the tree is balanced). Then you just read the aggregate statistic (sum in this case) from the root of this new tree. Then you can merge them together in the end.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to get range sum with MST ?

→ Reply