http://poj.org/problem?id=3468線段數的構造，查詢，修改！
struct node{
int l,r,m;
long long sum;//當前區間的和
long long add;//區間需要加上的數值
}
題意：
給定n個數字A1,A2,..,An，Q個操作。
C x y z,把區間x y內的數都加上z
Q x y，求區間x y內所有數的和。
總結：
基礎代碼一定要對，調試了半天，最后發現是swap(x,y,t)寫錯了?。。?！
WA了一次，數據是long long才行，要分析清楚數據范圍！??！
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define swap(x,y,t) (t=x,x=y,y=t)
#define clr(list) memset(list,0,sizeof(list))
#define LL long long
#define maxn 200005
using namespace std;
struct node{
int l,r,m;
LL sum;
LL add;
} tree[2*maxn];
int a[maxn];
LL build(int l,int r,int root)
{
tree[root].l=l;
tree[root].r=r;
tree[root].m=(l+r)/2;
tree[root].add=0;
if (l==r)
{
tree[root].sum=a[l];
return tree[root].sum;
}
long long sum_l=build(l,(l+r)/2,root*2);
long long sum_r=build((l+r)/2+1,r,root*2+1);
tree[root].sum=sum_l+sum_r;
return tree[root].sum;
}
int insert(int l,int r,int add,int root)
{
if (l<=tree[root].l && r>=tree[root].r)
{
tree[root].add+=add;
tree[root].sum+=add * (tree[root].r-tree[root].l+1);
return 0;
}
if (tree[root].add) //向下更新
{
tree[2*root].sum+=tree[root].add * (tree[root*2].r-tree[root*2].l+1);
tree[2*root].add+=tree[root].add;
tree[2*root+1].sum+=tree[root].add * (tree[root*2+1].r-tree[root*2+1].l+1);
tree[2*root+1].add+=tree[root].add;
tree[root].add=0;
}
if (l<=tree[root].m)
insert(l,r,add,root*2);
if (r>tree[root].m)
insert(l,r,add,root*2+1);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum; //這里回溯啊
return 0;
}
LL search(int l,int r,int root)
{
if (l<=tree[root].l && r>=tree[root].r)
return tree[root].sum;
if (tree[root].add) //向下更新
{
tree[2*root].sum+=tree[root].add * (tree[root*2].r-tree[root*2].l+1);
tree[2*root].add+=tree[root].add;
tree[2*root+1].sum+=tree[root].add * (tree[root*2+1].r-tree[root*2+1].l+1);
tree[2*root+1].add+=tree[root].add;
tree[root].add=0;
}
LL sum_l=0,sum_r=0;
if (l<=tree[root].m)
sum_l=search(l,r,2*root);
if (r>tree[root].m)
sum_r=search(l,r,2*root+1);
return sum_l+sum_r;
}
int main()
{
int n,m;
int x,y,z;
int tmp;
char ch;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
for (int i=1;i<=m;i++)
{
scanf("\n%c",&ch);
if (ch=='C')
{
scanf("%d%d%d",&x,&y,&z);
if (x>y)
swap(x,y,tmp);
insert(x,y,z,1);
}
else
{
scanf("%d%d",&x,&y);
if (x>y)
swap(x,y,tmp);
printf("%I64d\n",search(x,y,1));
}
}
return 0;
}