记录编号	359268	评测结果	AAAAAAAAAA
题目名称	求和问题	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.654 s
提交时间	2016-12-21 21:05:44	内存使用	17.45 MiB

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define int long long
inline void read(int &x) {
	char c;bool flag(0);
	while((c = getchar())<'0' || c>'9')if(c=='-') flag = 1;
	x = c - '0';
	while((c = getchar())>='0' && c<='9') x = x*10+c-'0'; 
	if (flag) x = -x;
} 

inline char getc() {char c = getchar();while(c==' '||c=='\n') c=getchar();}
 
void reout(int x) {if(x >= 10) reout(x/10);putchar(x%10+'0');}
void out(int x) {if(x < 0) putchar('-'),x = -x;reout(x);putchar('\n');}
 
#define MAXX 500000*5
#define inf 21474836

int n,M,x,y,k;
int sum[MAXX];

void push_up(int o) {sum[o] = sum[o<<1]+sum[o<<1|1];}

void build() {
	for (M=1; M<=n+1; M<<=1);
	for (int i = M+1; i <= M+n; i++) read(sum[i]);
	for (int i = M-1; i; i--) push_up(i); 
}

void add(int x,int v) {
	sum[M+x] += v;while(x) push_up(x>>=1); 
}

int Sum(int x,int y,int ans = 0) {
	for (x=x+M-1,y=y+M+1;x^y^1;x>>=1,y>>=1) {
		if(~x&1) ans += sum[x^1];
		if(y&1) ans += sum[y^1];
	} return ans;
} 

void work() {
	int m;read(n);build();read(m);
	while(m--) read(x),read(y),out(Sum(x,y));	
}

signed main() {
	freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    work(); 
	return 0;
}