题解(线段树区间修改模板及lazytag) 寒假3 C.简单整数问题（多错题）
zhouwc
2018-02-25 09:39:13
问题 C: 简单整数问题
时间限制: 2 Sec 内存限制: 128 MB
[提交][状态][讨论版]
题目描述
罗老师给大家N个数字，用A1, A2, …, AN表示，然后有两个操作：
1. C a b c： 表示给区间[ Aa, Ab ]， 每个数上增加c的值
2. Q a b：表示询问区间[ Aa, Ab ]的总和
输入
输入N Q表示N个数和Q个操作
然后输入一行 N个数，表示每个数字初始值
然后输入Q行，每行一个操作，如题目描述的两种操作
输出
对于每个询问操作，输出区间和
样例输入
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
样例输出
4
55
9
15
提示
【数据规模和约定】
1<=N,Q<=100000
-100000000<=Ai<=100000000
-10000<=c<=10000
题解
题解1（罗老师本来在题目中写着的）
tr[i]表示线段树上的结点，表示[st, ed]的未更新前的区间和
ad[i]表示线段树上的[st, ed]更新了多少值
难点在于，更新的值需要传递下去，回更新上来
```cpp
void pushDown(int p)
{
ad[p+p]+=ad[p]; ad[p+p+1]+=ad[p];
ad[p]=0LL;
}
void pullUp(int p,int len)
{
tr[p]=tr[p<<1]+ad[p<<1]*(len-(len>>1))+tr[p<<1|1]+ad[p<<1|1]*(len>>1);
}
```
题解2（我自己写的，并且经过无数次错误之后）
哎，就差那么一点点就对了。。。这本是一道模板题。。。
结果找了一个下午+一个晚上。改了无数个地方，最后还是请罗老师帮忙。
细节决定成败啊。。。
错误原因：1、addv，tree，dfs（int）必须都要开成longlong，我忽略了addv。
2、在dfs中，原本A,B两题直接可以return，而这道题因为要修改区间。有这个懒惰标记（lazytag）的影响，需要在查找值的时候，顺带改变当前初始的一些值。即我们会因为addv【p】的下移，导致addv【p】=0。且tree【p】的值也会因为下面两个儿子的值的改变而改变，所以需要对tree【p】的值进行重新计算（在dfs，update中都需要），而在dfs中，我直接加上了重新计算这个语句。但是却忽略了在前面的查找（二分）中，直接把dfs的只给return了。这直接造成了后面这个重新计算语句的失效，而addv的值已经被剪掉了，这是问题之所在。
最后，我想说，细节决定成败！！！
本来的错误代码：错误！！！
```cpp
#include<stdio.h>
using namespace std;
long long tree[400005];
int a[100005],n,m,x,y,addv[400005];
char b[3];
/*
void change(int p,int l,int r,int q,int v)//单点修改部分
{
if (l==r)
{
tree[p]=v;
return;
}
int mid=(l+r)/2;
if (q<=mid) change(p*2,l,mid,q,v);
else change(p*2+1,mid+1,r,q,v);
tree[p]=min(tree[p*2],tree[p*2+1]);
}
*/
void update(int l,int r,int p,int ql,int qr,int c)
{
if (l==ql&&qr==r)
{
addv[p]=addv[p]+c;
return;
}
addv[p*2]+=addv[p];
addv[p*2+1]+=addv[p];
addv[p]=0;
int mid=(l+r)/2;
/*
if (l<=mid) update(l,mid,p*2,ql,qr,c);
if (r>mid) update(mid+1,r,p*2+1,ql,qr,c);
tree[p]=tree[p*2]+tree[p*2+1]+addv[p*2]*(mid-l)+addv[p*2+1]*(r-mid);
*/
if (qr<=mid) { update(l,mid,p*2,ql,qr,c); }else
if (ql>mid) {update(mid+1,r,p*2+1,ql,qr,c);}else
{
update(l,mid,p*2,ql,mid,c);
update(mid+1,r,p*2+1,mid+1,qr,c);
}
tree[p]=tree[p*2]+tree[p*2+1]+addv[p*2]*(mid-l+1)+addv[p*2+1]*(r-mid);
}
long long dfs(int l,int r,int p,int s,int t)
{
if (l==s&&r==t) return tree[p]+addv[p]*(r-l+1);
else
{
int mid=(l+r)/2;
addv[p*2]+=addv[p];
addv[p*2+1]+=addv[p];
addv[p]=0;
if (t<=mid) return dfs(l,mid,p*2,s,t); else
if (s>mid) return dfs(mid+1,r,p*2+1,s,t); else
{
return dfs(l,mid,p*2,s,mid)+dfs(mid+1,r,p*2+1,mid+1,t);
}
tree[p]=tree[p*2]+tree[p*2+1]+addv[p*2]*(mid-l+1)+addv[p*2+1]*(r-mid);
}
}
void build(int l,int r,int p)
{
if (l==r)
{
tree[p]=a[l];
return;
}
else
{
int mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
tree[p]=tree[p*2]+tree[p*2+1];
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
int k=0;
for (int i=1;i<=m;i++)
{
scanf("%s",b);
if (b[0]=='Q')
{
scanf("%d%d",&x,&y);
printf("%lld\n",dfs(1,n,1,x,y));
k++;
}
else
{
int z=0;
scanf("%d%d%d",&x,&y,&z);
update(1,n,1,x,y,z);
}
}
}
```
经过修改后的AC代码，在//即一开始错误之处。
```cpp
#include<stdio.h>
using namespace std;
long long tree[400005];
int a[100005],n,m,x,y;
long long addv[400005]; //addv也改成long long 类型
char b[3];
/*
void change(int p,int l,int r,int q,int v)//单点修改部分
{
if (l==r)
{
tree[p]=v;
return;
}
int mid=(l+r)/2;
if (q<=mid) change(p*2,l,mid,q,v);
else change(p*2+1,mid+1,r,q,v);
tree[p]=min(tree[p*2],tree[p*2+1]);
}
*/
void update(int l,int r,int p,int ql,int qr,int c)
{
if (l==ql&&qr==r)
{
addv[p]=addv[p]+c;
return;
}
addv[p*2]+=addv[p];
addv[p*2+1]+=addv[p];
addv[p]=0;
int mid=(l+r)/2;
/*
if (l<=mid) update(l,mid,p*2,ql,qr,c);
if (r>mid) update(mid+1,r,p*2+1,ql,qr,c);
tree[p]=tree[p*2]+tree[p*2+1]+addv[p*2]*(mid-l)+addv[p*2+1]*(r-mid);
*/
if (qr<=mid) { update(l,mid,p*2,ql,qr,c); }else
if (ql>mid) {update(mid+1,r,p*2+1,ql,qr,c);}else
{
update(l,mid,p*2,ql,mid,c);
update(mid+1,r,p*2+1,mid+1,qr,c);
}
tree[p]=tree[p*2]+tree[p*2+1]+addv[p*2]*(mid-l+1)+addv[p*2+1]*(r-mid);
}
long long dfs(int l,int r,int p,int s,int t)
{
if (l==s&&r==t) return tree[p]+addv[p]*(r-l+1);
else
{
int mid=(l+r)/2;
addv[p*2]+=addv[p];
addv[p*2+1]+=addv[p];
addv[p]=0;
long long ret=0; //设置一个返回值变量
if (t<=mid) ret=dfs(l,mid,p*2,s,t);
else if (s>mid) ret=dfs(mid+1,r,p*2+1,s,t);
else{
ret=dfs(l,mid,p*2,s,mid)+dfs(mid+1,r,p*2+1,mid+1,t); //这里不能return
}
tree[p]=tree[p*2]+tree[p*2+1]+addv[p*2]*(mid-l+1)+addv[p*2+1]*(r-mid);
return ret;
}
}
void build(int l,int r,int p)
{
if (l==r)
{
tree[p]=a[l];
return;
}
else
{
int mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
tree[p]=tree[p*2]+tree[p*2+1];
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
int k=0;
for (int i=1;i<=m;i++)
{
scanf("%s",b);
if (b[0]=='Q')
{
scanf("%d%d",&x,&y);
printf("%lld\n",dfs(1,n,1,x,y));
k++;
}
else
{
int z=0;
scanf("%d%d%d",&x,&y,&z);
update(1,n,1,x,y,z);
}
}
}
```