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

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.

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.

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.

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);
}

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.

How to get range sum with MST ?