HDU - 1166 敌兵布阵（线段树，树状数组）

HDU - 1166 敌兵布阵

线段树

#include<stdio.h>
#include<string.h>
const int N = 50010;
struct Node
{
    int l,r,sum;
}tr[N*4];
int w[N],n;
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int u,int l,int r)
{
    if(l==r) tr[u]={
    l,r,w[l]};else{
    tr[u]={
    l,r};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}
void update(int u,int x,int d)
{
    if(tr[u].l==x&&tr[u].r==x) tr[u].sum+=d;else{
    int mid=tr[u].l+tr[u].r>>1;if(x<=mid) update(u<<1,x,d);if(x>mid) update(u<<1|1,x,d);pushup(u);}
}
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;else{
    int mid=tr[u].l+tr[u].r>>1;int res=0;if(l<=mid) res+=query(u<<1,l,r);if(r>mid) res+=query(u<<1|1,l,r);return res;}
}
int main()
{
    int T,t=1;scanf("%d",&T);while(T--){
    printf("Case %d:\n",t++);int n;scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&w[i]);build(1,1,n);char op[10];while(scanf("%s",op)!=EOF){
    if(strcmp(op,"End")==0) break;int l,r;scanf("%d%d",&l,&r);if(strcmp(op,"Add")==0) update(1,l,r);if(strcmp(op,"Sub")==0) update(1,l,-r);if(strcmp(op,"Query")==0) printf("%d\n",query(1,l,r));}}return 0;
}

树状数组

#include<stdio.h>
#include<string.h>const int N = 50010;
int n,c[N];int add(int x,int y){
    for(;x<=n;x+=(x&-x)) c[x]+=y;}
int getsum(int x){
    int res=0;for(;x;x-=(x&-x)) res+=c[x];return res;}int main()
{
    int T,t=1;scanf("%d",&T);while(T--){
    memset(c,0,sizeof c);printf("Case %d:\n",t++);scanf("%d",&n); for(int i=1;i<=n;i++) {
    int x;scanf("%d",&x);add(i,x);}char op[10];while(scanf("%s",op)!=EOF){
    if(strcmp(op,"End")==0) break;int l,r;scanf("%d%d",&l,&r);if(strcmp(op,"Add")==0) add(l,r);if(strcmp(op,"Sub")==0) add(l,-r);if(strcmp(op,"Query")==0) printf("%d\n",getsum(r)-getsum(l-1));}}return 0;
}