[线段树成段更新]poj 3468

题意：

?????? 给出一串n个数，每次操作分为两种，分别是对[i,j]区间上的数字加上一个值，查询[i,j]区间上所有数字的和

?

思路：

?????? 对于这种一次要对一个区间进行更新的问题，用单点更新肯定会超时，这里设定一个add值，意思是如果更新的区间和当前区间左右完全相等的时候，用add值记录本应向下加上去的节点，并返回

?

#include<iostream>
#include<cstring>
#include<cstdio>
const int nMax = 100010;
typedef long long ll;
using namespace std;
struct{
    int l,r;
    ll sum,add;
}node[3 * nMax];
int num[nMax];
ll ans;
void build(int l , int r , int u){
    node[u].l = l;
    node[u].r = r;
    node[u].add = 0;
    if(l == r){
        node [u].sum = num[r];
        return;
    }
    int m = (l + r) >> 1;
    build(l , m , u * 2);
    build(m + 1 ,r , u * 2 + 1);
    node[u].sum = node[u*2].sum + node[u * 2 + 1].sum;
}
void update(int left , int right ,int p , int u){
    if(node[u].l == left && node[u].r == right){
        node[u].add += p;
        return;
    }
    node[u].sum += (right - left + 1 )* p;
    int m = (node[u].r + node[u].l)>>1;
    if(left <= m){
        update(left , min(right ,node[u*2].r), p, u*2);
    }
    if(right >= m+1){
        update(max(left ,m+1) , right , p ,u*2 + 1);
    }
}


void query(int left ,int right ,int u){
    int l = node[u].l;
    int r = node[u].r;
    ans += (right-left+1)* node[u].add;
    if(l == left && r == right){
        ans += node[u].sum;
        return ;
    }
    int m = (node[u].r + node[u].l)>>1;
    if(right <= m){
        query(left , right , u*2);
        return;
    }
    if(left >= m+1){
        query(left , right , u*2+1);
        return;
    }
    query(left , m , u*2);
    query(m+1 , right , u*2 + 1);
}
int main(){
    int n, m ,i ,a , b ,c;char str[5];
    while(scanf("%d%d",&n,&m)!=EOF){
        for(i=1; i<= n; i++){
            scanf("%d",&num[i]);
        }
        build(1, n, 1);
        while(m--){
            scanf("%s",str);
            if(str[0] == ‘C‘){
                scanf("%d%d%d",&a,&b,&c);
                update(a ,b ,c , 1);
            }else{
                ans = 0;
                scanf("%d%d",&a,&b);
                query(a , b , 1);
                printf("%I64d\n",ans);
            }
        }
    }
    return 0;
}

?

[线段树成段更新]poj 3468

原文：http://bbezxcy.iteye.com/blog/2161207