不知道哪里有问题
求巨佬
by sindorei @ 2018-07-17 11:23:27
@[sindorei](/space/show?uid=68625) 您要知道线段树这种东西调不出来的
建议重构
by Lstdo @ 2018-07-17 11:36:10
@[sindorei](/space/show?uid=68625) 需要注意几个问题
1. 查询时,也要看是否标记下传。
2. 父亲标记下传时,不能直接赋值,要累加
3. 开long long
自己比对不同,总结反思~~~
```
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
long long A[N],tree[N<<2],tag[N<<2];
void pushdown(int left,int right,int root){
tag[root*2]+=tag[root];//标记向左右分发;
tag[root*2+1]+=tag[root];
int mid=(left+right)/2;
tree[root*2]+=(mid-left+1)*tag[root];//左侧的儿子值是左侧单元个数*标记的值加上它本来的;
tree[root*2+1]+=(right-mid)*tag[root];//右侧的儿子值是左侧单元个数*标记的值加上它本来的;
tag[root]=0;//标记清空
}
void create(int left,int right,int root){
tag[root]=0;
if (left==right){//如果长度为零,即是单元;
tree[root]=A[left];
return;
}
int mid=(left+right)/2;
create(left,mid,root*2);//创建左侧;
create(mid+1,right,root*2+1);//创建右侧;
tree[root]=tree[2*root]+tree[root*2+1];//树根是左侧值加右侧值;
return;
}
void add(int left,int right,int root,int x,int y,long long k){
if (y<left||x>right) return;//无交集,返回 0;
if (y>=right&&x<=left) {//被包含;
tree[root]=tree[root]+k*(right-left+1);//本区间总和加 k*区间中单元个数;
tag[root]=tag[root]+k;//标记加k
return;
}
if (tag[root]) pushdown(left,right,root);//标记不为零
int mid=(left+right)/2;
add(left,mid,root*2,x,y,k);//加在左侧;
add(mid+1,right,root*2+1,x,y,k);//加在右侧;
tree[root]=tree[root*2]+tree[root*2+1];//树根更新为左加右
return;
}
long long query(int left,int right,int root,int x,int y){
if (x>right||y<left) return 0;//无交集,返回 0;
if (x<=left&&y>=right) return tree[root];//被包含,返回总和;
if (tag[root]) pushdown(left,right,root);
int mid=(left+right)/2;
return query(left,mid,root*2,x,y)+query(mid+1,right,root*2+1,x,y);//左侧加右侧;
}
int main(){
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++){
cin>>A[i];
}
create(1,n,1);
for (int x,y,z,i=0;i<m;i++){
cin>>z>>x>>y;
long long k;
if (z==1){
cin>>k;
add(1,n,1,x,y,k);//add(总区间左,总区间右,下标,求区间左,求区间右,值);
}
if (z==2){
cout<<query(1,n,1,x,y)<<endl;//query(总区间左,总区间右,下标,求区间左,求区间右);
}
}
return 0;
}
```
by da32s1da @ 2018-07-17 11:40:08
@[luositing](/space/show?uid=53930)
谢谢
by sindorei @ 2018-07-17 11:51:48
@[da32s1da](/space/show?uid=50092)
谢谢
by sindorei @ 2018-07-17 11:52:03
谢谢各位,过了。
by sindorei @ 2018-07-17 12:03:19