POJ 3468 A Simple Problem with Integers（線段樹基礎）

需要注意的是記錄sum和lazy延時標識變量也要是64位整數，因為有乘法。

#include <iostream>   
#include <algorithm>   
#include <cmath>   
#include <cstdio>   
#include <cstdlib>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <set>   
#include <queue>   
#include <stack>   
#include <climits>//形如INT_MAX一類的   
#define MAX 100050   
#define INF 0x7FFFFFFF   
#define REP(i,s,t) for(int i=(s);i<=(t);++i)   
#define ll long long   
#define mem(a,b) memset(a,b,sizeof(a))   
#define mp(a,b) make_pair(a,b)   
#define L(x) x<<1   
#define R(x) x<<1|1   
# define eps 1e-5   
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛   
using namespace std;  
  
struct node {  
    int r,l,mid;  
    __int64 lazy,sum;  
}edge[4*MAX];  
  
int a[MAX];  
void up(int num) {  
    edge[num].sum = edge[L(num)].sum + edge[R(num)].sum;  
}  
  
void build(int l,int r,int num) {  
    edge[num].l = l;  
    edge[num].r = r;  
    edge[num].mid = (l+r) >> 1;  
    edge[num].lazy = 0;  
    if(l == r) {  
        edge[num].sum = a[l];  
        return ;  
    }  
    build(l,edge[num].mid,L(num));  
    build(edge[num].mid+1,r,R(num));  
    //   
    up(num);  
}  
  
void down(int num) {  
    if(edge[num].lazy) {  
        edge[L(num)].lazy += edge[num].lazy;  
        edge[R(num)].lazy += edge[num].lazy;  
        edge[L(num)].sum += (edge[L(num)].r - edge[L(num)].l + 1) * edge[num].lazy;  
        edge[R(num)].sum += (edge[R(num)].r - edge[R(num)].l + 1) * edge[num].lazy;  
        edge[num].lazy = 0;  
    }  
}  
  
void update(int l,int r,int num,__int64 k) {  
    if(l <= edge[num].l && r >= edge[num].r) {  
        edge[num].lazy += k;  
        edge[num].sum += (edge[num].r - edge[num].l + 1) * k;  
        return ;  
    }  
    down(num);  
    if(r <= edge[num].mid) {  
        update(l,r,L(num),k);  
    }  
    else if(l > edge[num].mid) {  
        update(l,r,R(num),k);  
    }  
    else {  
        update(l,edge[num].mid,L(num),k);  
        update(edge[num].mid + 1,r,R(num),k);  
    }  
    up(num);  
}  
  
__int64 query(int l,int r,int num) {  
    if(l <= edge[num].l && r >= edge[num].r) {  
        return edge[num].sum;  
    }  
    down(num);  
    if(r <= edge[num].mid) {  
        return query(l,r,L(num));  
    }  
    else if(l > edge[num].mid) {  
        return query(l,r,R(num));  
    }  
    else {  
        return query(l,edge[num].mid,L(num)) + query(edge[num].mid + 1,r,R(num));  
    }  
}  
int main() {  
  
    int n,m,b,c;  
    __int64 d;  
    char str[3];  
    scanf("%d%d",&n,&m);  
    for(int i=1; i<=n; i++) {  
        scanf("%d",&a[i]);  
    }  
    build(1,n,1);  
    for(int i=0; i<m; i++) {  
        scanf("%s",str);  
        if(str[0] == 'Q') {  
            scanf("%d%d",&b,&c);  
            printf("%I64d\n",query(b,c,1));  
        }  
        if(str[0] == 'C') {  
            scanf("%d%d%I64d",&b,&c,&d);  
  
            update(b,c,1,d);  
        }  
    }  
    return 0;  
}  

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一類的
#define MAX 100050
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛
using namespace std;

struct node {
    int r,l,mid;
    __int64 lazy,sum;
}edge[4*MAX];

int a[MAX];
void up(int num) {
    edge[num].sum = edge[L(num)].sum + edge[R(num)].sum;
}

void build(int l,int r,int num) {
    edge[num].l = l;
    edge[num].r = r;
    edge[num].mid = (l+r) >> 1;
    edge[num].lazy = 0;
    if(l == r) {
        edge[num].sum = a[l];
        return ;
    }
    build(l,edge[num].mid,L(num));
    build(edge[num].mid+1,r,R(num));
    //
    up(num);
}

void down(int num) {
    if(edge[num].lazy) {
        edge[L(num)].lazy += edge[num].lazy;
        edge[R(num)].lazy += edge[num].lazy;
        edge[L(num)].sum += (edge[L(num)].r - edge[L(num)].l + 1) * edge[num].lazy;
        edge[R(num)].sum += (edge[R(num)].r - edge[R(num)].l + 1) * edge[num].lazy;
        edge[num].lazy = 0;
    }
}

void update(int l,int r,int num,__int64 k) {
    if(l <= edge[num].l && r >= edge[num].r) {
        edge[num].lazy += k;
        edge[num].sum += (edge[num].r - edge[num].l + 1) * k;
        return ;
    }
    down(num);
    if(r <= edge[num].mid) {
        update(l,r,L(num),k);
    }
    else if(l > edge[num].mid) {
        update(l,r,R(num),k);
    }
    else {
        update(l,edge[num].mid,L(num),k);
        update(edge[num].mid + 1,r,R(num),k);
    }
    up(num);
}

__int64 query(int l,int r,int num) {
    if(l <= edge[num].l && r >= edge[num].r) {
        return edge[num].sum;
    }
    down(num);
    if(r <= edge[num].mid) {
        return query(l,r,L(num));
    }
    else if(l > edge[num].mid) {
        return query(l,r,R(num));
    }
    else {
        return query(l,edge[num].mid,L(num)) + query(edge[num].mid + 1,r,R(num));
    }
}
int main() {

    int n,m,b,c;
    __int64 d;
    char str[3];
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
    }
    build(1,n,1);
    for(int i=0; i<m; i++) {
        scanf("%s",str);
        if(str[0] == 'Q') {
            scanf("%d%d",&b,&c);
            printf("%I64d\n",query(b,c,1));
        }
        if(str[0] == 'C') {
            scanf("%d%d%I64d",&b,&c,&d);

            update(b,c,1,d);
        }
    }
    return 0;
}