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;
}
