首页 > 代码库 > HDU 1166 敌兵布阵 （线段树 单点更新）
HDU 1166 敌兵布阵 （线段树 单点更新）
题目链接
线段树掌握的很差，打算从头从最简单的开始刷一波， 嗯。。就从这个题开始吧！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <cstdlib> 6 #include <algorithm> 7 const int maxn = 50000+10; 8 using namespace std; 9 int a[maxn], n;10 struct line11 {12 int l, r, val;13 }tr[maxn<<2];14 15 void build(int o, int l, int r)16 {17 tr[o].l = l; tr[o].r = r;18 if(l == r)19 {20 tr[o].val = a[l];21 return;22 }23 int mid = (l+r)>>1;24 build(2*o, l, mid);25 build(2*o+1, mid+1, r);26 tr[o].val = tr[2*o].val+tr[2*o+1].val;27 }28 int query(int o, int l, int r)29 {30 if(tr[o].l==l && tr[o].r==r)31 return tr[o].val;32 int mid = (tr[o].l+tr[o].r)>>1;33 if(r <= mid) query(2*o, l, r);34 else if(l > mid) query(2*o+1, l, r);35 else36 return (query(2*o, l, mid)+query(2*o+1, mid+1, r));37 }38 void update(int o, int p, int add)39 {40 if(tr[o].l==tr[o].r&&tr[o].l==p)41 {42 tr[o].val += add;43 return;44 }45 int mid = (tr[o].l+tr[o].r)>>1;46 if(p<=mid) update(2*o, p, add);47 else update(2*o+1, p, add);48 tr[o].val = tr[2*o].val+tr[2*o+1].val;49 }50 int main()51 {52 int t, i, ca = 1;53 int p, add, l, r;54 char s[20];55 scanf("%d", &t);56 while(t--)57 {58 scanf("%d", &n);59 for(i = 1; i <= n; i++)60 scanf("%d", &a[i]);61 printf("Case %d:\n", ca++);62 63 build(1, 1, n);64 while(~scanf("%s", s))65 {66 if(strcmp(s, "End")==0) break;67 if(s[0]==‘Q‘)68 {69 scanf("%d%d", &l, &r);70 printf("%d\n", query(1, l, r));71 }72 if(s[0]==‘A‘)73 {74 scanf("%d%d", &p, &add);75 update(1, p, add);76 }77 if(s[0]==‘S‘)78 {79 scanf("%d%d", &p, &add);80 update(1, p, -add);81 }82 }83 }84 return 0;85 }
注释的代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <cstdlib> 6 #include <algorithm> 7 const int maxn = 50000+10; 8 using namespace std; 9 int a[maxn], n;10 struct line11 {12 int l, r, val; //val表示该区间的和13 }tr[maxn<<2];14 15 void build(int o, int l, int r) //o代表当前节点编号16 {17 tr[o].l = l; tr[o].r = r;18 if(l == r)19 {20 tr[o].val = a[l];21 return;22 }23 int mid = (l+r)>>1;24 build(2*o, l, mid);25 build(2*o+1, mid+1, r);26 tr[o].val = tr[2*o].val+tr[2*o+1].val; //建树把值从下往上加起来27 }28 int query(int o, int l, int r) //求l到r的和29 {30 if(tr[o].l==l && tr[o].r==r) //节点的区间吻合返回31 return tr[o].val;32 int mid = (tr[o].l+tr[o].r)>>1;33 if(r <= mid) query(2*o, l, r);34 else if(l > mid) query(2*o+1, l, r);35 else36 return (query(2*o, l, mid)+query(2*o+1, mid+1, r)); //横跨了区间37 }38 void update(int o, int p, int add) //对p节点增加add39 {40 if(tr[o].l==tr[o].r&&tr[o].l==p)41 {42 tr[o].val += add;43 return;44 }45 int mid = (tr[o].l+tr[o].r)>>1;46 if(p<=mid) update(2*o, p, add);47 else update(2*o+1, p, add);48 tr[o].val = tr[2*o].val+tr[2*o+1].val; //找到值以后的更新49 }50 int main()51 {52 int t, i, ca = 1;53 int p, add, l, r;54 char s[20];55 scanf("%d", &t);56 while(t--)57 {58 scanf("%d", &n);59 for(i = 1; i <= n; i++)60 scanf("%d", &a[i]);61 printf("Case %d:\n", ca++);62 63 build(1, 1, n);64 while(~scanf("%s", s))65 {66 if(strcmp(s, "End")==0) break;67 if(s[0]==‘Q‘)68 {69 scanf("%d%d", &l, &r);70 printf("%d\n", query(1, l, r));71 }72 if(s[0]==‘A‘)73 {74 scanf("%d%d", &p, &add);75 update(1, p, add);76 }77 if(s[0]==‘S‘)78 {79 scanf("%d%d", &p, &add);80 update(1, p, -add);81 }82 }83 }84 return 0;85 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。