Jishnu Banerjee - 1 year ago 299

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`

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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.

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**