hdoj 1166 敌兵布阵

hdoj 1166 敌兵布阵

暴力超时，这道题可以用线段树做，因为更新的是单个节点，我们也可以用数组数组来做，我将两种方法的代码都给出

数组数组最适宜的用途就是区间求和和点的更新，但树状数组并不适用于区间的更新问题，也不是做不到，比较麻烦且难理解，有兴趣的可以看看这个

//树状数组#includeint n,ans[50005],f[50005];int lowbit(int n){ return n&(-n);}void add(int i,int v){ while(i <= n) { ans[i] += v; i += lowbit(i); }}int query(int n){ int s = 0; while(n) { s += ans[n]; n -= lowbit(n); } return s;}int main(){ int t; scanf("%d",&t); for(int j = 1;j <= t; j++) { scanf("%d",&n); for(int l = 1; l <= n;l++) { scanf("%d",&f[l]); f[l] += f[l-1]; } for(int l = 1; l <= n; l++) ans[l] = f[l]-f[l-lowbit(l)]; printf("Case %d:\n",j); while(1) { char s[20]; int a,b; scanf("%s",s); if (s[0] == 'E') break; scanf("%d%d",&a,&b); if (s[0] == 'A') add(a,b); if (s[0] == 'S') add(a,-b); if (s[0] == 'Q') printf("%d\n",query(b)-query(a-1)); } } return 0;}

//线段树解法#include #include #define maxn 50005struct node{ int l, r, m; int sum;}tree[maxn<<2];int a[maxn];void build(int l, int r, int o){ tree[o].l = l; tree[o].r = r; int m = (l+r)>>1; tree[o].m = m; if (l == r) { tree[o].sum = a[l]; return; } build(l, m, o<<1); build(m+1, r, (o<<1)+1); tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum; }void update(int l, int v, int o){ tree[o].sum += v; if (tree[o].l == l && tree[o].r == l) return; if (l <= tree[o].m) update(l, v, o<<1); else update(l, v, (o<<1)+1);}int query(int l, int r, int o){ if (tree[o].l == r && tree[o].r == r) return tree[o].sum; if (tree[o].m >= r) return query(l, r, o<<1); else if (tree[o].m

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。