Jishnu Banerjee - 4 months ago 115

C 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`

`int`

`0`

`summation`

`st`

`ed`

The

`summation`

Answer

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

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.