11592: 【原1592】求和

题目

题目描述

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

Description

子虚年乌有月，亡是国兵败，亡是公欲割地以求和。

已知：

亡是国疆域内有\(N\)座封人口数为\({X_1,X_2,…,X_N}\)的封城。

亡是公有\(M\)个割地方案，他会给出割地的边界 \(l,r\)，每个方案中包含的领地是连续的。

对于每个方案包含的人口数量，亡是公希望你帮他求和。

Input Format

第一行有两个整数\(N,M\) ，分别代表封城个数和方案个数。

接下来一行 \(N\) 个数代表每个城市的人口\( {X_1,X_2,…,X_N}\)。

接下来 \(M\) 行，每行两个整数 \(l,r\)。代表求和区间为 \([l,r]\)。

Output Format

对于每个方案，输出区间内人口数的总和，每个询问输出一行。

Sample Input

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

Sample Output

101
11
90
244

Limits

对于\(100\%\)的数据，\(\forall i, X_i\in [0,2147483647),l,r\in [1,N]\)。

对于\(60\%\)的数据，\(M,N \leq 10^4\)

对于\(100\%\)的数据，\(M,N \leq 10^6\)

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))

inline int read() {

    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);
    n = read(); p = read();
    int _num, _num2;
    long long _ans;
    for (int i = 1; i <= n; ++i) {
//      scanf("%d", &_num);
        _num = read();
        int tmp = i;
        while (tmp <= n) {
            _c[tmp] += _num;
            tmp += low_bit(tmp);
        }
    }

    while (p--) {
//      scanf("%d%d", &_num, &_num2);
        _num = read(); _num2 = read();
        _ans = sum(_c, _num2) - sum(_c, _num - 1);
        printf("%lld\n", _ans);
    }

    return 0;
}