title: Is there any faster implementation for this Splay Tree range sum?
body: <p>I have coded a splay tree. The nodes are represented like this.</p>
  
  <pre><code>struct Node{
      Node *l;  /// The left  Node
      Node *r;  /// The right Node
      int v;    /// The Value
  };
  </code></pre>
  
  <p>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 <code>summation.</code></p>
  
  <pre><code>void summation(Node *R, int st, int ed)
  {
      if(!R) return;
      if(R-&gt;v &lt; st){        /// should not call left side
          summation(R-&gt;r, st, ed);
      }
      else if(R-&gt;v &gt; ed){   /// should not call right side
          summation(R-&gt;l, st, ed);
      }
      else{                /// should call both side
          ret+=R-&gt;v;
          summation(R-&gt;l, st, ed);
          summation(R-&gt;r, st, ed);
      }
      return;
  }
  </code></pre>
  
  <p><code>ret</code> is a global <code>int</code> variable which is initialized to <code>0</code> before calling the <code>summation</code> function. The two parameters <code>st</code> &amp; <code>ed</code> defines the range (inclusive).</p>
  
  <p>The <code>summation</code> function works at a complexity of O(n). Can anyone suggest any faster implementation for this??</p>