首页 > 代码库 > POJ 3468 线段树裸题
POJ 3468 线段树裸题
这些天一直在看线段树，因为临近期末，所以看得断断续续，弄得有些知识点没能理解得很透切，但我也知道不能钻牛角尖，所以配合着刷题来加深理解。
然后，这是线段树裸题，而且是最简单的区间增加与查询，我参考了ACdreamer的模板，在此基础上自己用宏定义来精简了一下代码：
1 #include<cstdio> 2 typedef long long LL; 3 #define root int rt, int l, int r 4 #define lson rt*2, l, mid 5 #define rson rt*2+1, mid+1, r 6 #define makemid int mid= (l+r)>>1 7 int a,b; 8 LL c; 9 10 struct tree {11 LL add,sum;12 } s[400003];13 14 void build(root) {15 s[rt].add= 0;16 if(l==r){17 scanf("%lld",&s[rt].sum);18 return ;19 }20 makemid ;21 build(lson);22 build(rson);23 s[rt].sum= s[rt*2].sum+s[rt*2+1].sum;24 }25 26 inline void pushdown(int rt, int len) {27 int ls= rt*2, rs= ls+1;28 const LL &c= s[rt].add;29 s[ls].add += c;30 s[rs].add += c;31 s[ls].sum += c*(len-len/2);32 s[rs].sum += c*(len/2);33 s[rt].add= 0;34 }35 36 void update(root) {37 if(a<=l && r<=b){38 s[rt].add+= c;39 s[rt].sum+= c*(r-l+1);40 return ;41 }42 if(s[rt].add) pushdown(rt,r-l+1);43 makemid ;44 if(a<=mid) update(lson);45 if(b>mid) update(rson);46 s[rt].sum= s[rt*2].sum+s[rt*2+1].sum;47 }48 49 LL query(root) {50 if(a<=l && r<=b) return s[rt].sum;51 if(s[rt].add) pushdown(rt,r-l+1);52 makemid ;53 LL res= 0;54 if(a<=mid) res+= query(lson);55 if(b>mid) res+= query(rson);56 return res;57 }58 59 int main(){60 int n,q;61 while(~scanf("%d%d",&n,&q)){62 build(1,1,n);63 while(q--){64 getchar();65 if(getchar()==‘Q‘){66 scanf("%d%d",&a,&b);67 printf("%lld\n",query(1,1,n));68 }69 else {70 scanf("%d%d%lld",&a,&b,&c);71 update(1,1,n);72 }73 }74 }75 return 0;76 }
原样的代码是：
1 #include<cstdio> 2 typedef long long LL; 3 LL c; 4 int a,b; 5 6 struct tree{ 7 LL add,sum; 8 } s[400003]; 9 10 void build(int rt, int l, int r){11 s[rt].add= 0;12 if(l==r){13 scanf("%lld",&s[rt].sum);14 return ;15 }16 int mid= (l+r)>>1;17 build(rt*2,l,mid);18 build(rt*2+1,mid+1,r);19 s[rt].sum= s[rt*2].sum+s[rt*2+1].sum;20 }21 22 inline void pushdown(int rt, int len){23 if(s[rt].add){24 int ls= rt*2, rs= ls+1;25 s[ls].add += s[rt].add;26 s[rs].add += s[rt].add;27 s[ls].sum += s[rt].add*(len-len/2);28 s[rs].sum += s[rt].add*(len/2);29 s[rt].add= 0;30 }31 }32 33 void update(int rt, int l, int r){34 if(a<=l && r<=b){35 s[rt].add+= c;36 s[rt].sum+= c*(r-l+1);37 return ;38 }39 pushdown(rt,r-l+1);40 int mid= (l+r)>>1;41 if(a<=mid) update(rt*2,l,mid);42 if(b>mid) update(rt*2+1,mid+1,r);43 s[rt].sum= s[rt*2].sum+s[rt*2+1].sum;44 }45 46 LL query(int rt, int l, int r){47 if(a<=l && r<=b) return s[rt].sum;48 pushdown(rt,r-l+1);49 int mid= (l+r)>>1;50 LL res= 0;51 if(a<=mid) res+= query(rt*2,l,mid);52 if(b>mid) res+= query(rt*2+1,mid+1,r);53 return res;54 }55 56 int main(){57 int n,q;58 while(~scanf("%d%d",&n,&q)){59 build(1,1,n);60 while(q--){61 getchar();62 if(getchar()==‘Q‘){63 scanf("%d%d",&a,&b);64 printf("%lld\n",query(1,1,n));65 }66 else {67 scanf("%d%d%lld",&a,&b,&c);68 update(1,1,n);69 }70 }71 }72 return 0;73 }
线段树，不断进取中~~
POJ 3468 线段树裸题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。