首页 > 代码库 > HDU-1166 敌兵布阵
HDU-1166 敌兵布阵
数据结构中的线段树,第一次接触线段树,,,
就简单的介绍一下线段树吧
就我自己的理解吧和二叉树差不多,,虽然我现在还不了解线段树(逃
线段树是一种二叉搜索树,将一个区间还分成一些单元区间,再通过二分的方法不断的划分,最终划成单个区间,比如1到16吧,根节点为1(rt),划分成左子树和右子树,根结点分别为2(rt<<1)和3(rt<<1|1代表的区间分别为1到8和9到16,1到8在继续划分,左子树根结点4,区间1到4,右子树根结点5,区间5到8,依次类推,,,
分为建树,更新和查询
//建树 l区间的起点,r区间的终点,rt根结点
void build(int l,int r,int rt){
if(l==r) {
scanf(“%d",&tree[rt]);
reurn ;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(miod+1,rt<<1|1);
tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
//更新 L 更新的区间的起点,R 更新的区间的终点,c 要更新的值,
void update(int l,int r,int L,int R,int rt,int c){
if(l==r) {
tree[rt]+=c;
return ;
}
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,L,R,rt<<1,c);
if(r>mid) update(mid+1,r,L,R,rt<<1|1,c);
tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
//查询 L 查询的起点,R查询的终点,
int query(int L,int R,int l, int r,int rt){
if(L<=l&&r<=R){
return tree[rt];
}
int mid=(l+r)>>1;
int ans=0;
if(L<=mid) ans+=query(L,R,l,mid,rt<<1);
if(r>mid) ans+=query(L,R,mid+1,r,rt<<1|1);
return ans;
}
//好像写成区间更新了,嗯,不过这样会TLE,需要一个延迟标记,lazy[maxn];
,,,,,,
代码
# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>
using namespace std;
const int maxn=5e4+5;
int sum[maxn*4];
void build(int root,int l,int r){
if(l==r) {
scanf("%d",&sum[root]);
return ;
}
build(root<<1,l,(l+r)/2);
build(root<<1|1,(l+r)/2+1,r);
sum[root]=sum[root<<1]+sum[root<<1|1];
}
void update(int p,int add,int l,int r,int root){
if(l==r){
sum[root]+=add;
return;
}
if(p<=(l+r)/2) update(p,add,l,(l+r)/2,root<<1);
else update(p,add,(l+r)/2+1,r,root<<1|1);
sum[root]=sum[root<<1]+sum[root<<1|1];
}
int query(int L,int R,int l,int r,int root){
if(L<=l&&r<=R) return sum[root];
int cnt=0;
if(L<=(l+r)/2) cnt+=query(L,R,l,(l+r)/2,root<<1);
if(R>(l+r)/2) cnt+=query(L,R,(l+r)/2+1,r,root<<1|1);
return cnt;
}
int main(){
int t,l=0;
scanf("%d",&t);
while(l<t){
int n;
scanf("%d",&n);
build(1,1,n);
char qu[10];
printf("Case %d:\n",++l);
while(scanf("%s",qu)){
if(qu[0]==‘E‘) break;
int a,b;
scanf("%d %d",&a,&b);
if(qu[0]==‘A‘) update(a,b,1,n,1);
if(qu[0]==‘S‘) update(a,-b,1,n,1);
if(qu[0]==‘Q‘) {
int ans=query(a,b,1,n,1);
printf("%d\n",ans);
}
}
}
return 0;
}
HDU-1166 敌兵布阵