69 lines
1.3 KiB
C++
69 lines
1.3 KiB
C++
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
#define AS(c){if(!(c)){cerr<<"assert failed: "<<#c<<endl;return -1;}}
|
|
|
|
void build(int t[],int a[],int s,int e,int n){
|
|
if(s==e){
|
|
t[n]=a[s];
|
|
return;
|
|
}
|
|
int m=s+((e-s)>>1);
|
|
build(t,a,s,m,n*2);
|
|
build(t,a,m+1,e,n*2+1);
|
|
t[n]=t[n*2]+t[n*2+1];
|
|
}
|
|
|
|
int search(int t[],int s,int e,int n,int l,int r){
|
|
if(l<=s&&e<=r){
|
|
return t[n];
|
|
}
|
|
if(e<l||r<s){
|
|
return 0;
|
|
}
|
|
int m = s+((e-s)>>1);
|
|
return search(t, s, m, n*2,l, r)+search(t, m+1, e, n*2+1, l, r);
|
|
}
|
|
|
|
#ifdef OITEST
|
|
#endif
|
|
#ifndef OITEST
|
|
#endif
|
|
|
|
int main(int argc,char *argv[]){
|
|
#ifdef OITEST
|
|
AS(argc==3)
|
|
ifstream ifile(argv[1]);
|
|
ifstream afile(argv[2]);
|
|
AS(ifile.is_open()==true);
|
|
AS(afile.is_open()==true);
|
|
stringstream ss;
|
|
#define cout ss
|
|
#define cin ifile
|
|
#endif
|
|
#ifndef OITEST
|
|
#endif
|
|
|
|
int n;
|
|
cin>>n;
|
|
int k=n*4+1;
|
|
int t[(int)1e8];
|
|
int arr[(int)1e8];
|
|
for(int i=1;i<=n;i++){
|
|
cin>>arr[i];
|
|
}
|
|
build(t, arr, 1, n, 1);
|
|
int m;
|
|
cin>>m;
|
|
for(int i=1;i<=m;i++){
|
|
int l,r;
|
|
cin>>l>>r;
|
|
cout<<search(t, 1, n, 1, l, r)<<endl;
|
|
#ifdef OITEST
|
|
int myans,cans;
|
|
ss>>myans;
|
|
afile>>cans;
|
|
AS(myans==cans)
|
|
#endif
|
|
}
|
|
} |