# 11592: 【原1592】求和

### 题目描述

author: Spy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1592

# Description

## Sample Input

6 4
46 97 11 90 35 38
3 4
3 3
4 4
1 4


## Sample Output

101
11
90
244


## WashSwang's solution

#include <iostream>
using namespace std;
typedef long long ll;
ll t[4000000],ans[1000000];
int n,m,k,l,r;
inline int lowbit(int x){ return x&-x;}
void update(int x,int k){
while (x<=n){
t[x]+=k;
x+=lowbit(x);
}
}
ll query(int x){
ll sum=0;
while (x>0){
sum+=t[x];
x-=lowbit(x);
}
return sum;
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i){
scanf("%d",&k);
update(i,k);
}
for (int i=0;i<m;++i){
scanf("%d%d",&l,&r);
ans[i]=query(r)-query(l-1);
}
for (int i=0;i<m;++i)
printf("%lld\n",ans[i]);
return 0;
}


## yyong119's solution

#include <cstdio>
const int MAX_N = 1000010;
using namespace std;
long long _c[MAX_N];
#define low_bit(x) (x & (-x))

char ch; int ret = 0;
for (ch = getchar(); ch<'0' || ch>'9'; ch = getchar());
for (; ch >= '0'&& ch <= '9'; ret = ret * 10 + ch - '0', ch = getchar());
return ret;
}

long long sum(long long _c[], int spot) {

long long _sum = 0;
while (spot > 0) {
_sum += _c[spot];
spot -= low_bit(spot);
}

return _sum;
}

int main() {

int n, p;
//  scanf("%d%d", &n, &p);
int _num, _num2;
long long _ans;
for (int i = 1; i <= n; ++i) {
//      scanf("%d", &_num);
int tmp = i;
while (tmp <= n) {
_c[tmp] += _num;
tmp += low_bit(tmp);
}
}

while (p--) {
//      scanf("%d%d", &_num, &_num2);