CSUMQ - Cumulative Sum Query( POINTER STRUCTURE FOR RANGE QUERY)

CSUMQ - Cumulative Sum Query

no tags 

William Macfarlane wants to look at an array.

You are given a list of N numbers and Q queries. Each query is specified by two numbers i and j; the answer to each query is the sum of every number between the range [i, j] (inclusive).

Note: the query ranges are specified using 0-based indexing.

Input

The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N-1).

Output

For each query, output the answer to that query on its own line in the order the queries were made.

Example

Input:
3
1 4 1
3
1 1
1 2
0 2

Output:
4
5
6

===================================EDITORIAL========================================================

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
class seg
{
   
    public:
     ll sum;
     seg* lf, *rt;
     seg()
     {
              lf=NULL;
     rt=NULL;
     sum=0; 
  }
      
};

int a[100010];

seg* build(seg *root,int s,int e)
{
          if(s>e)
          {
            
                    return root;
    }
          if(s==e)
          {
                  
               root->sum=a[s];
               return root;
    }
    int mid=(s+e)/2;
    root->lf=new seg();
    root->lf=build(root->lf,s,mid);
    root->rt=new seg();
    root->rt=build(root->rt,mid+1,e);
    root->sum=root->lf->sum+root->rt->sum;
    return root;
    
}

ll query(seg * root, int s,int e, int ql ,int qh)
{
      if(s>e|| s>qh || e<ql )
      return 0;
      if(s>=ql && e<=qh)
      {
         return root->sum;
   }
   int mid=(s+e)/2;
   ll q1=query(root->lf,s,mid,ql,qh);
   ll q2=query(root->rt,mid+1,e,ql,qh);
   return q1+q2;
}
int main()
{
        int n;
        cin>>n;
        int q;
        for(int i=0;i<n;i++)
        {
          scanf("%d",&a[i]);
     }
     seg *root=new seg();
     root=build(root,0,n-1);
     cin>>q;
     for(int i=0;i<q;i++)
     {
        int l,r;
        scanf("%d %d",&l,&r);
        ll res=query(root,0,n-1,l,r);
        printf("%lld\n",res);
     }
     return 0;
     
}

---