Jishnu Banerjee - 1 year ago 343
C Question

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

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??

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.