2011-06-28 16:38:02Morris

d799. 区间求和 (樹狀數組版本)

d799. 区间求和

內容 :

在本题描述之前,首先衷心感谢morris1028为线段树的高级数据结构算法打开了大门!

给你N个数据,不断地改变这N个数据的同时也不停地问你某个区间中所有元素的和!

輸入說明 :

只有一笔测试数据。

第一行是N(0<N<=500000),接下来有N个数a[i][j](0<=a[i,j]<=32767)。

然后是一个数字Q(0<Q<=500000),接下来有Q组要求和询问。

每组要求或询问的格式是:首先是一个数 v (v=1或2),

若v=1则表示是要求,接下来有三个数据 x y k (0<x<=y<=N且0<=k<=1000),表示从第x个数据至第y个数据每个都加上k;

若v=2则表示是询问,接下来有两个数据 x y (0<x<=y<=N),你得输出从第x个数据至第y个数据的所有元素的和。

輸出說明 :

如果是要求,则不用输出;

如果是询问,则输出所要求的元素之和。

範例輸入 :

4
1 2 3 4
5
2 1 3
1 1 3 1
2 1 3
1 1 4 1
2 1 4

範例輸出 :

6
9
17

提示 :

32767×500000>2147483647

出處 :

线段树 (管理:liouzhou_101)



作法 : 樹狀數組
http://kenby.iteye.com/blog/962159
上面的網站,已經寫得很透徹了,在此就不多言了

/**********************************************************************************/
/*  Problem: d799 "区间求和" from 线段树                                   */
/*  Language: C                                                                   */
/*  Result: AC (1192ms, 15896KB) on ZeroJudge                                     */
/*  Author: morris1028 at 2011-06-28 15:57:26                                     */
/**********************************************************************************/


#include<stdio.h>
#define N 500001
long long sum[N];
long long c1[N], c2[N];
int A[N], lowbit[N], n;
int Input() {
    char cha;
    unsigned int x = 0;
    while(cha = getchar())
        if(cha != ' ' && cha != '\n') break;
    x = cha-48;
    while(cha = getchar()) {
        if(cha == ' ' || cha == '\n') break;
        x = x*10 + cha-48;
    }
    return x;
}
long long query(long long C[], int i) {
    long long sum = 0;
    while(i > 0) {
        sum += C[i];
        i -= lowbit[i];
    }
    return sum;
}
void update(long long C[], int i, long long k) {
    while(i <= n) {
        C[i] += k;
        i += lowbit[i];
    }
}
main() {
    int a, q, i, j, k;
    long long Ans;
    char v;
    for(a = 1; a < N; a++)
        lowbit[a] = a & (-a);
    scanf("%d", &n);
        for(a = 1; a <= n; a++)
            A[a] = Input();
        for(a = 1; a <= n; a++)
            sum[a] = sum[a-1] + A[a];
        scanf("%d", &q);
        getchar();
        while(q--) {
            v = getchar();
            if(v == '1') {
                i = Input(), j = Input(), k = Input();
                update(c1, i, k);
                update(c1, j+1, -k);
                update(c2, i, k*i);
                update(c2, j+1, -k*(j+1));
            }
            else {
                i = Input(), j = Input();
                Ans = sum[j] - sum[i-1];
                Ans += (j+1)*query(c1, j) - query(c2, j);
                Ans -=  i*query(c1, i-1) - query(c2, i-1);
                printf("%lld\n", Ans);
            }
        }
    return 0;
}