http://poj.org/problem?id=3468
题意：给n个数字，从A1 …………An m次命令，Q是查询，查询a到b的区间和，c是更新，从a到b每个值都增加x。
思路：这是一个很明显的线段树的题目，就是线段树的用区间更新就可以，我也是第一次用。。
#include <stdio.h>
#include <string.h>
#define maxn 100050 long long arra[ maxn ]; struct note{ //要用long long 类型的，不然会爆数据的。 long long sum,c; }segtree[ maxn * ]; void build(int root , int instart , int iend) //插入操作。
{
segtree[ root ].c = ;
if(instart == iend)
segtree[ root ].sum = arra[ instart ];
else
{
int mid = (instart + iend)/;
build( root * , instart ,mid );
build( root * + , mid + , iend );
segtree[ root ].sum = segtree[ root * ].sum + segtree[ root * + ].sum;
}
} void pushdown(int root,int sta , int en ) //延迟标记。
{
if(segtree[ root ].c != )
{
segtree[ root * ].c += segtree[ root ].c;
segtree[ root * + ].c += segtree [ root ].c;
int mid = (sta + en) / ;
segtree[ root * ] .sum += segtree[ root ].c*( mid - sta + );
segtree[ root * + ].sum += segtree[ root ].c *( en - mid );
segtree[ root ].c = ;
}
} long long Find(int root , int ranges , int rangee , int goals ,int goale) //查找。查找时也需要对延迟标记进行更新。
{
if( goals > rangee || goale < ranges)
return ;
if( rangee <= goale && ranges >= goals)
return segtree[ root ].sum;
pushdown(root,ranges,rangee);
int mid = (rangee+ranges) / ;
return Find(root * , ranges , mid , goals ,goale)+ Find(root * + , mid + , rangee , goals , goale );
} void update(int root , int sta, int en,int x,int y,int val) //更新。
{
if( x > en || y < sta)
return ;
if( x <= sta && y >= en)
{
segtree[ root ].sum += val*( en - sta + ) ;
segtree[ root ].c += val ;
return ;
}
pushdown(root,sta,en);
int mid = ( sta + en ) / ;
update ( root * , sta , mid , x ,y ,val );
update ( root * + , mid + , en , x , y , val );
segtree [ root ].sum = segtree[ root * ].sum + segtree[ root * + ].sum;
} int main()
{
//freopen("in.txt","r",stdin);
int m,n,a,b,c;
char x;
scanf("%d%d",&m,&n);
for( int i = ; i <= m ; i++ )
scanf("%lld",&arra[i]);
build(,,m);
for( int i = ; i <= n ; i++ )
{
scanf("%s",&x);
if(x=='Q')
{
scanf("%d%d",&a,&b);
printf("%lld\n",Find(,,m,a,b));
}
else
{
scanf("%d%d%d",&a,&b,&c);
update(,,m,a,b,c);
}
}
return ;
}