敌兵布阵 HDU1166

基础线段树

#include<cstdio>

#include<iostream>

using namespace std;

int n,p,a,b,m,x,y,ans;

struct node

{

    int l,r,v,f;

}tree[400001];

 void build(int k,int l,int r)//建树

{

    tree[k].l=l,tree[k].r=r;

    if(tree[k].l==tree[k].r)

    {

        scanf("%d",&tree[k].v);

        return;

    }

    int m=(l+r)/2;

    build(k*2,l,m);

    build(k*2+1,m+1,r);

    tree[k].v=tree[k*2].v+tree[k*2+1].v;

}

void down(int k)//标记下传

{

    tree[k*2].f+=tree[k].f;

    tree[k*2+1].f+=tree[k].f;

    tree[k*2].v+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);

    tree[k*2+1].v+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);

    tree[k].f=0;

}

int ask_point(int k,int x)//单点查询

{

    if(tree[k].l==tree[k].r)

    {

        return tree[k].v;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/2;

    if(x<=m) ask_point(k*2,x);

    else ask_point(k*2+1,x);

}

void change_point(int k,int x,int v)//单点修改

{

    if(tree[k].l==tree[k].r)

    {

        tree[k].v+=v;

        return;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/2;

    if(x<=m) change_point(k*2,x,v);

    else change_point(k*2+1,x,v);

    tree[k].v=tree[k*2].v+tree[k*2+1].v;

}

void ask_interval(int k,int a,int b)//区间查询

{

    if(tree[k].l>=a&&tree[k].r<=b)

    {

        ans+=tree[k].v;

        return;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/2;

    if(a<=m) ask_interval(k*2,a,b);

    if(b>m) ask_interval(k*2+1,a,b);

}

void change_interval(int k,int a,int b,int v)//区间修改

{

    if(tree[k].l>=a&&tree[k].r<=b)

    {

        tree[k].v+=(tree[k].r-tree[k].l+1)*v;

        tree[k].f+=v;

        return;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/2;

    if(a<=m) change_interval(k*2,a,b,v);

    if(b>m) change_interval(k*2+1,a,b,v);

    tree[k].v=tree[k*2].v+tree[k*2+1].v;

}

int main()

{

   int cas;cin>>cas;

    int flag=0;

    while(cas--)

    {   printf("Case %d:\n",++flag);

        int n;scanf("%d",&n);

        build(1,1,n);

        char s[2000];

        int x,y;

        while(scanf("%s",s)==1)

        {   ans=0;

            if(s[0]=='E')break;

            scanf("%d%d",&x,&y);

            if(s[0]=='A')change_point(1,x,y);

            if(s[0]=='S')change_point(1,x,-y);

            if(s[0]=='Q'){ask_interval(1,x,y);printf("%d\n",ans);}

        }

    }

    return 0;

 

}

树状数组

#include<bits/stdc++.h>

using namespace std;

int c[];

int n;

int lowbit(int i)

{

    return i&-i;

}

void update(int i,int val)

{

    while(i<=n)

    {

        c[i]+=val;

        i+=lowbit(i);

    }

}

int sum(int i)

{

    int ans=;

    while(i>)

    {

        ans+=c[i];

        i-=lowbit(i);

    }

    return ans;

}

int main()

{

    int cas;cin>>cas;

   for(int k=;k<=cas;k++)

    {

      memset(c,,sizeof(c));

      cin>>n;

      for(int i=;i<=n;i++)

      {

          int x;scanf("%d",&x);

          update(i,x);

      }

       printf("Case %d:\n",k);

       char s[];

       while(scanf("%s",s)==)

       {

           if(s[]=='E')break;

           int a,b;scanf("%d%d",&a,&b);

           if(s[]=='A')update(a,b);

           if(s[]=='S')update(a,-b);

           if(s[]=='Q')printf("%d\n",sum(b)-sum(a-));

       }

    }

}