poj 3486 A Simple Problem with Integers（树状数组第三种模板改段求段）

/*

    树状数组第三种模板（改段求段）不解释！ 

       不明白的点这里：here！

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define N 100005

using namespace std;

typedef long long LL;

LL ss[N], B[N], C[N];

int n, m;

void addB(int x, int k){//B[i]表示被1...i整体一共加了多少的总和 

    for(int i=x; i<=n; i+=i&(-i))  B[i]+=x*k; 

}

void addC(int x, int k){//1....x节点的每个节点的增量 

    for(int i=x; i>0; i-=i&(-i))   C[i]+=k;

LL sumB(int x){

    LL s=0;

    for(int i=x; i>0; i-=i&(-i)) s+=B[i];

    return s;

LL sumC(int x){//x节点总共的增量 

    for(int i=x; i<=n; i+=i&(-i)) s+=C[i];

LL sum(int x){

    return x==0 ? 0 : sumC(x)*x + sumB(x-1); 

void update(int a, int b, int c){

    addB(b, c);

    addC(b, c);

    if(a-1>0){

        addB(a-1, -c); 

        addC(a-1, -c);

    }

int main(){

    int m;

    while(scanf("%d%d", &n, &m)!=EOF){

        for(int i=1; i<=n; ++i){

            scanf("%lld", &ss[i]);

            ss[i]+=ss[i-1];

        } 

        char ch[2];

        int a, b, c;

        while(m--){

            scanf("%s", ch); 

            if(ch[0]=='Q'){

                scanf("%d%d", &a, &b);

                printf("%lld\n", ss[b]-ss[a-1]+sum(b)-sum(a-1));

            }

            else{

                scanf("%d%d%d", &a, &b, &c);

                update(a, b, c); 

        }

    return 0;

本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3969029.html，如需转载请自行联系原作者