poj 3468
题目大意：给定Q(1 ≤ Q≤ 100,000)个数A1,A2… AQ,，以及可能多次进行的两个操作:
1)对某个区间Ai … Aj的个数都加n(n可变）2) 求某个区间Ai … Aj的数的和
2) 求某个区间Ai … Aj的数的和
解决：线段树
/*
线段树的区间有两种形式，第一种是[1,2][2,3]，第二种是[1,1],[2,2]，在这里，由于我们查询的区间和是不能相交的，所以只能采用第二中形式，
*/
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long intt;
struct node
{
int l,r;
intt sum,inc;
};
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
#define M(x,y) ((x+y)>>1)
const int N=1000005;
node tree[2*N];
int num[N];//保存第i个数的值
/*第二种形式的建树过程*/
void build(int t,int l,int r)
{
tree[t].l=l;
tree[t].r=r;
tree[t].inc=0;
if(l==r){tree[t].sum=num[l];return;}//判断为叶子节点的话，我们直接通过num中的数据给sum
int mid=M(l,r);
build(L(t),l,mid);
build(R(t),mid+1,r);//建立右子树是为mid+1
tree[t].sum=tree[L(t)].sum+tree[R(t)].sum;//若左右子树都建立好了，根节点的sum值可以求出来了
}
/*
查询过程：我采用的是如果当前区间在查找区间中，我们就算出sum值（sum值和inc的值不要忘了）并直接返回结果，否则，往下查找，往下查找时判断当前区间是否有增量，若有增量的话，将增量传至左右孩子，将当前区间的sum值计算出来更新，并将当前的增量置为0
*/
intt query(int t,int l,int r)
{
intt sum=0;
if(tree[t].l>=l && tree[t].r<=r)
{
sum+=(r-l+1)*tree[t].inc+tree[t].sum;
return sum;
}
if(tree[t].inc)
{
tree[L(t)].inc+=tree[t].inc;
tree[R(t)].inc+=tree[t].inc;
tree[t].sum+=(tree[t].r-tree[t].l+1)*tree[t].inc;//此处不能写成(r-l+1)*tree[t].inc因为如果此处有inc
// 说明这个节点的每个值都要加上inc的值当然是这个区间的长度乘以inc
tree[t].inc=0;
}
int mid=M(tree[t].l,tree[t].r);
if(r<=mid)sum+=query(L(t),l,r);
else if(l>mid)sum+=query(R(t),l,r);
else
{
sum+=query(L(t),l,mid);
sum+=query(R(t),mid+1,r);
}
return sum;
}
/*
更新区间：更新区间只是更新inc值
若为包含的区间，将inc值添加就行了，否则的话，一定是当前区间过大了，直接将当前区间的sum值
加上增量
*/
void updata(int t,int l, int r,intt inc)
{
if(tree[t].l>=l && tree[t].r<=r){tree[t].inc+=inc;return;}
else
{
tree[t].sum+=(r-l+1)*inc;
}
int mid=M(tree[t].l,tree[t].r);
if(r<=mid)updata(L(t),l,r,inc);
else if(l>mid)updata(R(t),l,r,inc);
else {updata(L(t),l,mid,inc); updata(R(t),mid+1,r,inc);}
}
int main()
{
int i,n,q,a,b;
intt inc;
char cmd[10];
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)scanf("%d",num+i);
build(1,1,n);
while(q--)
{
getchar();
scanf("%s%d%d",cmd,&a,&b);
if(cmd[0]=='Q')printf("%I64d\n",query(1,a,b));
else
{
scanf("%I64d",&inc);//由于输入格式错误导致调试了一个小时
updata(1,a,b,inc);
}
}
system("pause");
return 0;
}