首页 > 代码库 > 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 敌兵布阵