poj3321——Apple Tree//树状数组

记住树状数组的基本操作：http://hi.baidu.com/wuxyy/blog/item/a4ad808b59be8bd2fd1f109d.html

http://writeblog.csdn.net/PostEdit.aspx?entryId=6376639

int lowbit(int x)
{
   return x&(x^(x–1));
}
利用机器补码的特点，这个函数可以改得更方便
int lowbit(int i)
{
   return i&(-i);
}
如果要把a[n]增加m，可以通过调用如下函数实现
void add(int i,int v)
{
   while (i<=n)
   {
      a[i]+=v;
      i+=lowbit(i);
   }
}
如果要统计a[1]到a[n]之间的和，可以通过调用如下函数实现
int sum(int i)
{
   int s=0;
   while (i>0)
   {
      s+=a[i];
      i-=lowbit(i);
   }
   return s;
}

此题思路：将每个点定一个时间戳。比如题目中给的树dfs()之后，点1为1,6，点2为2,3，点3为4,5.这样，查询1时，统计1--6之间的apple，再将结果除以2即可。

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
#define maxn 1000005
int n,m;
class map
{
public:
	int v,next;
};
map g[maxn];
int head[maxn],cnt,c[maxn*2];
bool have[maxn];
class tree
{
public:
	int st,ed;
};
tree st[maxn];
void dfs(int v)
{
	st[v].st =++cnt;
	int i;
	for(i=head[v];i;i=g[i].next )
	{
		dfs(g[i].v );
	}
	st[v].ed =++cnt;
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int t,int v)
{
	while(t<maxn)
	{
		c[t]+=v;
		t+=lowbit(t);
	}
}
int getsum(int t)
{
	int s=0;
	while(t>0)
	{
		s+=c[t];
		t-=lowbit(t);
	}
	return s;
}
int main()
{
	int i,a,b,lsum,rsum;
	char ch;
	cnt=0;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&a,&b);
		g[++cnt].v =b;
		g[cnt].next =head[a];
		head[a]=cnt;
	}
	cnt=0;
	dfs(1);
	memset(have,true,sizeof(have));
	for(i=1;i<=n;i++)
	{
		add(st[i].st,1);
		add(st[i].ed,1);
	}
	scanf("%d",&m);
	getchar();
	while(m--)
	{
		scanf("%c %d",&ch,&a);
		getchar();
		if(ch=='Q')
		{
			lsum=getsum(st[a].st-1 );
			rsum=getsum(st[a].ed );
			printf("%d\n",(rsum-lsum)/2);
		}
		else if(ch=='C')
		{
			if(have[a])
			{
				have[a]=false;
				add(st[a].st ,-1);
				add(st[a].ed ,-1);
			}
			else 
			{
				have[a]=true;
				add(st[a].st ,1);
				add(st[a].ed ,1);
			}
		}
	}
	return 0;
}