题目大意
你有n个整数，A1、A2、…、AN。你需要处理两种操作。
- 将给定范围内的每个数字加上一个给定的值。
- 求一个给定范围内的数字的总和。
思路
线段树成段增减的模板题。
代码
#include
#include
using namespace std;
#define MAXSIZE 100000
int total_edge,val[MAXSIZE+1];
struct node
{
long long total;
//区间属性，这里是total，表示区间元素和。
int left;
int right;
long long mark;
//mark表示延迟标记
}tree[MAXSIZE*3];
long long create(int root,int left,int right)
//以root为根节点建树。
{
tree[root].mark=0;
tree[root].left=left;
tree[root].right=right;
if(left==right)
return tree[root].total=val[left];
int middle=(left+right)/2;
return tree[root].total=create(2*root,left,middle)+create(2*root+1,middle+1,right);
}
void updata_mark(int root)
//更新root的子节点的延迟标记。
{
if(tree[root].mark)
{
tree[root].total+=tree[root].mark*(tree[root].right-tree[root].left+1);
if(tree[root].left!=tree[root].right)
{
tree[root*2].mark+=tree[root].mark;
tree[root*2+1].mark+=tree[root].mark;
}
tree[root].mark=0;
}
}
long long calculate(int root,int left,int right)
//以root为根节点的线段树中，求取区间[left,right]的元素和。
{
updata_mark(root);
if(tree[root].left>right||tree[root].right<left)
return 0;
if(left<=tree[root].left&&tree[root].rightright||tree[root].right<left)
return tree[root].total;
if(left<=tree[root].left&&tree[root].right<=right)
{
tree[root].mark+=val;
updata_mark(root);
return tree[root].total;
}
return tree[root].total=updata(2*root,left,right,val)+updata(2*root+1,left,right,val);
}
int main()
{
int n,q;
while(~scanf("%d%d",&n,&q))
{
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
create(1,1,n);
char op;
for(int i=0;i<q;i++)
{
scanf("\n%c",&op);
if(op=='Q')
{
int a,b;
scanf("%d%d",&a,&b);
printf("%I64d\n",calculate(1,a,b));
}
else
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
updata(1,a,b,c);
}
}
}
}