Complexity of range sum query in a quad tree
<p>I want to solve a problem that gives the (integral) coordinates of n points (n&lt;=10^5)
and asks q queries (q&lt;=10^4). In each query it gives the (integral) coordinates of two other points and we need to answer how many of the n points are located within the rectangle created by those two points. </p>

<p>(edit) Also the coordinates are huge (x,y &lt;= 10^9) (/edit) </p>

<p>I created a quad tree and then used this function to get the answer, however i get time limit exceeded (time limit = 2s). Is this approach too slow or have I done something wrong?</p>

<pre><code>int sum(int left, int right, int down, int up, int i=1, int begx=0, int endx=1e9, int begy=0, int endy=1e9)
{
    if (!i || left&gt;right || down&gt;up) return 0;
    if (left==begx &amp;&amp; right==endx &amp;&amp; down==begy &amp;&amp; up==endy) return num[i];
    int midx = (begx+endx)/2, midy = (begy+endy)/2;
    return  sum(left,min(midx,right),down,min(midy,up),child[i][0],begx,midx,begy,midy)
        +   sum(left,min(midx,right),max(midy+1,down),up,child[i][1],begx,midx,midy+1,endy)
        +   sum(max(midx+1,left),right,down,min(midy,up),child[i][2],midx+1,endx,begy,midy)
        +   sum(max(midx+1,left),right,max(midy+1,down),up,child[i][3],midx+1,endx,midy+1,endy);
}
</code></pre>

<p>If I comment this function out (and don't answer the queries, just add the points to the quad tree) I get an execution time of about 0.2 secs.
Array <code>num</code> stores the sum of a node and <code>child</code> stores the index of the four children of each node. Node 0 is dummy. The partitioning of a rectangle in children looks like this:</p>

<pre><code> ___
|1 3|
|0 2|
 ---
</code></pre>