Is there any faster implementation for this Splay Tree range sum?

Question

I have coded a splay tree. The nodes are represented like this.

struct Node{
    Node *l;  /// The left  Node
    Node *r;  /// The right Node
    int v;    /// The Value
};

Now, I need to know the summation of all the numbers in the tree within a certain range. For this, i implemented the following function named summation.

void summation(Node *R, int st, int ed)
{
    if(!R) return;
    if(R->v < st){        /// should not call left side
        summation(R->r, st, ed);
    }
    else if(R->v > ed){   /// should not call right side
        summation(R->l, st, ed);
    }
    else{                /// should call both side
        ret+=R->v;
        summation(R->l, st, ed);
        summation(R->r, st, ed);
    }
    return;
}

ret is a global int variable which is initialized to 0 before calling the summation function. The two parameters st & ed defines the range (inclusive).

The summation function works at a complexity of O(n). Can anyone suggest any faster implementation for this??

`void summation(Node *R, ...)` Node is not a type name. Are you using C++ ? — joop, Aug 08 '16 at 09:32
Node is the structure i've mentioned earlier in the question. — jbsu32, Aug 08 '16 at 11:19
Since you don't have a clue you must be using C++. (in C, `struct Node {...};` does **not** imply `typedef struct Node{...};` ) — joop, Aug 09 '16 at 10:40

Yerken · Accepted Answer · 2016-08-08T09:27:25.273

4

This is the splay tree implementation I did some time ago and tested against SPOJ evaluation system (written in C++) :

https://ideone.com/aQgEpF

This tree implementation supports what u are asking for (range sum in O(log(n)).

The key idea here is to use split and merge, to extract the subtree covering the range. Additionally each node contains a field sum, which is a sum of all keys in its subtree. The sum field is lazily evaluated and only relayed during split operation (along the splitting line), which allows not to go deeper into the levels not required to be calculated.

edited Aug 08 '16 at 09:27

answered Aug 08 '16 at 09:21

Yerken

1,944
1
14
18

Thanks a lot! this was exactly what i were trying to do! I had the idea, but couldn't implement in code. thanks again! – jbsu32 Aug 08 '16 at 11:42

score 1 · Answer 2 · edited May 23 '17 at 12:13

First, as a side-note, having summation not return anything, instead manipulating a global variable, is probably not such a great idea. You probably should consider omitting this global variable, and have the recursive function just return what it found (and have a call sum up the values returned by its further recursive calls, before returning this sum itself).

Regarding your specific question, you can optimize the summation operation by augmenting node metadata. This will reduce the summation operation's order of growth, without affecting the order of growth of the other operations. On the downside, this will somewhat reduce the speed of the other operations. It is up to you to decide if this tradeoff is good for you.

The basic idea is as follows:

Keep within each node another field indicating the sum of the items in the tree rooted at this node.
With some thought, you can see how to efficiently update this information when updating the tree.
With some further thought you can see how you can answer a range query using this metadata.

Thanks for the suggestion given in the first para. I'll keep that in mind. :) And, also thanks for the idea. It helped me a lot! — jbsu32, Aug 08 '16 at 11:40
You're very welcome. The other answer is basically an implementation of this, BTW. — Ami Tavory, Aug 08 '16 at 11:46

Is there any faster implementation for this Splay Tree range sum?

2 Answers2