POJ 3321 Apple Tree 树状数组第一题

浏览数：22 / 时间：2015年06月11日

第一次做树状数组，这个东西还是蛮神奇的，通过一个简单的C数组就可以表示出整个序列的值，并且可以用logN的复杂度进行改值与求和。

这道题目我根本不知道怎么和树状数组扯上的关系，刚开始我想直接按图来遍历来做，后来用树状数组做完都跑了600+MS，那样估计是TLE了。

做法就是用DFS把整个图重建一遍，代号小的点在叶子，代号大的点为根。记录每个根的起始点号为 idl，根点号为 idh，则求某个根的苹果和就直接调用树状数组的sum即可。

不过前提是要建好树，我一开始不明白为什么要建一颗标准树，即就是按1 2 3 4。。。。，每个点有一个苹果的递增的标准树，因为整个图并不是按这个标准来建得，2号点C值为1号和2号的和，但实际的树可能1号和2号都是叶子啊。。。。后来想清楚了，每次求和都是建立在某个根上，而这个根和它的所有孩子是符合标准树状数组的。

#include <cstdio>
#include <cstring>
#define N 100010
using namespace std;
int u[N],v[N],nt[N],ft[N],idh[N],idl[N],cnt,isapple[N],c[N];
void add(int a,int b)
{
    u[cnt]=a;
    v[cnt]=b;
    nt[cnt]=ft[a];
    ft[a]=cnt++;
}
int n;
void dfs(int x)
{
    idl[x]=cnt;
    if (ft[x]==-1)
    {
        idh[x]=cnt++;
        return;
    }
    for (int i=ft[x];i>=0;i=nt[i])
    {
        int nx=v[i];
        dfs(nx);
    }
    idh[x]=cnt++;
}
int lowbit(int x)
{
    return x & (-x);
}
void update(int x)
{
    int d;
    if (isapple[x])
    {
        d=-1;
        isapple[x]^=1;
    }
    else
    {
        d=1;
        isapple[x]^=1;
    }
    while (x<=n)
    {
        c[x]+=d;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int ret=0;
    while (x>0)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
int main()
{
    int m;
    while (scanf("%d",&n)!=EOF)
    {
        cnt=0;
        int a,b;
        memset(ft,-1,sizeof ft);
        memset(c,0,sizeof c);
        for (int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
        }
        cnt=1;
        dfs(1);
        for (int i=1;i<=n;i++)
        {
            isapple[i]=0;
            update(i);
        }
        //puts("pp");
        scanf("%d",&m);
        char ch[2];
        int nt;
        while (m--)
        {
          // puts("pass");
            scanf("%s%d",ch,&nt);
            //puts(ch);
            if (ch[0]==‘Q‘)
            {
                int ans=getsum(idh[nt])-getsum(idl[nt]-1);//求结果的时候就求根的sum以及最小叶子的前一点，相减就是该棵树的和，就跟前缀和一样的原理
                printf("%d\n",ans);
            }
            else
            {
                update(idh[nt]);
            }
            //getchar();
        }
    }
    return 0;
}