Jishnu Banerjee Jishnu Banerjee - 4 months ago 115
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??

Answer

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.