首页 > 代码库 > 对于在线段树上修改整段区间的理解
对于在线段树上修改整段区间的理解
第一题
HDU1698http://acm.hdu.edu.cn/showproblem.php?pid=1698
这是在区间上进行整段的修改操作，我们就用to[]数组代表修改的lazy标记
记住在构建树和在change函数中自顶向下更新的时候，一定要注意重新回去更新上层的节点，所以末尾需加上update（cur）
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define N 100005 5 int sum[4*N],to[4*N]; 6 7 void update(int x) 8 { 9 sum[x]=sum[x<<1]+sum[x<<1|1];10 }11 void build(int cur,int x,int y)12 {13 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;14 to[cur]=0;15 if(x==y){16 sum[cur]=1;17 return;18 }19 build(ls,x,mid);20 build(rs,mid+1,y);21 update(cur);22 }23 void pushdown(int cur,int x,int y)24 {25 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;26 if(to[cur]!=0){27 to[ls]=to[rs]=to[cur];28 sum[ls]=(mid-x+1)*to[cur];29 sum[rs]=(y-mid)*to[cur];30 to[cur]=0;31 }32 }33 void change(int cur,int x,int y,int s,int t,int v)34 {35 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;36 if(x>=s&&y<=t){37 sum[cur]=(y-x+1)*v;38 to[cur]=v;39 return;40 }41 pushdown(cur,x,y);42 if(mid>=s) change(ls,x,mid,s,t,v);43 if(mid+1<=t) change(rs,mid+1,y,s,t,v);44 update(cur);45 }46 void query(int cur,int x,int y,int s,int t,int &ans)47 {48 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;49 if(x>=s&&y<=t){50 ans+=sum[cur];51 return;52 }53 pushdown(cur,x,y);54 if(mid>=s) query(ls,x,mid,s,t,ans);55 if(mid+1<=t) query(rs,mid+1,y,s,t,ans);56 }57 int main()58 {59 int T,n,Q,a,b,c,ans;60 scanf("%d",&T);61 for(int i=1;i<=T;i++){62 ans=0;63 scanf("%d%d",&n,&Q);64 build(1,1,n);65 for(int j=0;j<Q;j++){66 scanf("%d%d%d",&a,&b,&c);67 change(1,1,n,a,b,c);68 }69 query(1,1,n,1,n,ans);70 printf("Case %d: The total value of the hook is %d.\n",i,ans);71 }72 return 0;73 }
第二题
POJ3468http://poj.org/problem?id=3468
这是在一段区间上添加值，所以与上题的操作不一样，对于每个相加的数，我们应该也不断将lazy节点累加，类似这种的累加操作，我们总是选择
用add[]数组作为lazy标记
当然这道题特别坑的是因为在累加过程中可以达到10000*100000这样子就超过了int的类型，我们就要用LL来定义sum[],add[]和ans
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 #define N 100005 6 #define LL long long 7 int a[N]; 8 LL sum[4*N],add[4*N]; 9 void update(int x)10 {11 sum[x]=sum[x<<1]+sum[x<<1|1];12 }13 void build(int cur,int x,int y)14 {15 add[cur]=0;16 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;17 if(x==y){18 sum[cur]=a[x];19 return;20 }21 build(ls,x,mid);22 build(rs,mid+1,y);23 update(cur);24 }25 void pushdown(int cur,int x,int y)26 {27 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;28 if(add[cur]!=0){29 add[ls]+=add[cur];30 add[rs]+=add[cur];31 sum[ls]+=(mid-x+1)*add[cur];32 sum[rs]+=(y-mid)*add[cur];33 add[cur]=0;34 }35 }36 void change(int cur,int x,int y,int s,int t,int v)37 {38 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;39 if(x>=s&&y<=t){40 sum[cur]+=(y-x+1)*v;41 add[cur]+=v;42 return;43 }44 pushdown(cur,x,y);45 if(mid>=s) change(ls,x,mid,s,t,v);46 if(mid<t) change(rs,mid+1,y,s,t,v);47 update(cur);48 }49 void query(int cur,int x,int y,int s,int t,LL &ans)50 {51 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;52 if(x>=s&&y<=t){53 ans+=sum[cur];54 return;55 }56 pushdown(cur,x,y);57 if(mid>=s) query(ls,x,mid,s,t,ans);58 if(mid<t) query(rs,mid+1,y,s,t,ans);59 }60 int main()61 {62 int q,n,x,y,z;63 char c;64 while(scanf("%d%d",&n,&q)!=EOF){65 for(int i=1;i<=n;i++) scanf("%d",&a[i]);66 build(1,1,n);67 for(int i=1;i<=q;i++){68 cin>>c;69 if(c==‘C‘){70 scanf("%d%d%d",&x,&y,&z);71 change(1,1,n,x,y,z);72 }73 else{74 scanf("%d%d",&x,&y);75 LL ans=0;76 query(1,1,n,x,y,ans);77 printf("%I64d\n",ans);78 }79 }80 }81 return 0;82 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。