题目链接:http://codevs.cn/problem/1082/
时间限制: 3 s 空间限制: 128000 KB

题目描述 Description

给你N个数，有两种操作：
1：给区间[a,b]的所有数增加X
2：询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，每行表示操作的个数，如果第一个数是1，后接3个正整数，表示在区间[a,b]内每个数增加X,如果是2，表示操作2询问区间[a,b]的和是多少。
pascal选手请不要使用readln读入

输出描述 Output Description

对于每个询问输出一行一个答案。

样例输入 Sample Input

3
1
2
3
2
1 2 3 2
2 2 3

样例输出 Sample Output

9

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000
1<=q<=200000

解题思路

树状数组模板，区间更新，区间查询。

#include <bits/stdc++.h>
using namespace std;
long long bits_0[200005], bits_1[200005], n;
int lowbit(int x) {
    return x & -x;
}
void Update(long long *bits, int i, long long k) {
    while (i <= n) {
        bits[i] += k;
        i += lowbit(i);
    }
}
long long PrefixSum(long long *bits, int i) {
    long long ans = 0;
    while (i > 0) {
        ans += bits[i];
        i -= lowbit(i);
    }
    return ans;
}
long long RangeSum(int left, int right) {
    long long ans = PrefixSum(bits_0, right) * right + PrefixSum(bits_1, right);
    return ans - PrefixSum(bits_0, left - 1) * (left - 1) - PrefixSum(bits_1, left - 1);
}
int main() {
    int q, del, judge, delta, left, right;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &delta);
        Update(bits_1, i, delta);
    }
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &judge);
        if (judge - 1) {
            scanf("%d%d", &left, &right);
            printf("%lld\n", RangeSum(left, right));
        }
        else {
            scanf("%d%d%d", &left, &right, &delta);
            Update(bits_0, left, delta);
            Update(bits_0, right + 1, -delta);
            Update(bits_1, left, 1ll * -delta * (left - 1));
            Update(bits_1, right + 1, 1ll * delta * right);
        }
    }
    return 0;
}