首页 > 代码库 > hdu1166
hdu1166
没有用到懒惰标记的线段树问题,不过通过这道题找到了不用数组就能找到写update的方法了
#include<iostream>#include<queue>#include<algorithm>#include<cstring>#include<cstdio>using namespace std;#define max 50010#define INF 0x3f3f3f3fint tree[max*3],ans;void build(int rt,int L,int R){ if(L== R) { scanf("%d",&tree[rt]); } else { int M = (L+R)/2; build(rt*2,L,M); build(rt*2+1,M+1,R); tree[rt]= tree[rt*2]+tree[rt*2+1]; }}void update(int rt,int L,int R,int p,int q){ if(L==R&&L == p) { tree[rt]+= q; } else { int M = (L+R)/2; if (p<=M) update(rt*2,L,M,p,q); else update(rt*2+1,M+1,R,p,q); tree[rt]= tree[rt*2]+tree[rt*2+1]; }}void query(int cur,int x,int y,int s,int t){ int mid = (x+y)>> 1,ls = cur<< 1,rs =cur<<1|1; if(x>= s&&y<= t) { ans += tree[cur]; return ; } //pushdown(cur,x,y); if(mid>= s) query(ls,x,mid,s,t); if(mid+1<= t) query(rs,mid+1,y,s,t);}int main(){ int n,a,b,c,count =0;scanf("%d",&n); while(n--) { memset(tree,0,sizeof(tree)); ans =0; count++; scanf("%d",&a); build(1,1,a); char s[10]; printf("Case %d:\n",count); while((scanf("%s",s)!= EOF)&&s[0]!=‘E‘) { ans =0; scanf("%d%d",&b,&c); if(s[0]==‘Q‘){query(1,1,a,b,c);printf("%d\n",ans);} else if(s[0]==‘A‘){ update(1,1,a,b,c); } else update(1,1,a,b,-c); } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。