HDOJ 1166 ---敌兵布阵

HDOJ 1166 ---敌兵布阵

今天刚刚学了线段树，原来还有点不理解，学习​​Yoangh​​学长的博客，感觉懂了它用数组构造树，和查询的整个过程

所以对我来说，这道题很好入门的题。

在代码前先介绍大神的线段树风格:

1： maxn是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn的最小2x的两倍。

2：lson和rson分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的。

3：结合lson和rson的预定义可以很方便。

4：PushUP(int rt)是把当前结点的信息更新到父结点。

5：PushDown(int rt)是把当前结点的信息更新给儿子结点rt表示当前子树的根(root),也就是当前所在的结点。

代码：

#includeusing namespace std;#define MAXN 51100int cnt[MAXN*4];void Build(int l,int r,int rt)//rt是数组cnt的下标，从根节点开始 { if( l==r){ scanf("%d",&cnt[rt]); return ; } int mid=(l+r)>>1; Build(l,mid,rt<<1); // rt<<1 = 2*rt; Build(mid+1,r,rt<<1|1); //rt<<1|1 = 2*rt+1 ; cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];}void Update(int i,int add,int l,int r,int rt){ if( l==r){ cnt[rt]+=add; return ; } int mid=(l+r)>>1; if(i<=mid) Update(i,add,l,mid,rt<<1); else Update(i,add,mid+1,r,rt<<1|1); cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];}int Query(int L,int R,int l,int r,int rt){ if( L<=l&&R>=r) return cnt[rt]; int sum=0; int mid=(l+r)>>1; if(L<=mid) sum+=Query(L,R,l,mid,rt<<1); if(R>mid) sum+=Query(L,R,mid+1,r,rt<<1|1); return sum;}int main() { int i,t,n,c,l,r; char str[10]; scanf("%d",&t); for( c=1; c<=t; c++){ memset(cnt,0,sizeof(cnt)); scanf("%d",&n); Build(1,n,1); printf("Case %d:\n",c); while( true){ scanf("%s",str); if( str[0]=='E') break;//结束 if( str[0]=='Q'){//查询 scanf("%d%d",&l,&r); printf("%d\n",Query(l,r,1,n,1)); } else if( str[0]=='A'){//删减 scanf("%d%d",&i,&l); Update(i,l,1,n,1); } else{ scanf("%d%d",&i,&l); Update(i,-l,1,n,1); } } } return 0;}

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