poj3321

树状数组

题意：给定一棵树，某些节点上有苹果，多次询问各子树上的节点数，并且在询问的中途随时可能新增和删除苹果。

分析：dfs遍历树的同时，对每个点标注时间，每个点有一个开始时间和一个结束时间，把这两个时间当做下标，该点的苹果个数（1或0）填入数组的两个对应位。子树中结点的时间段一定是根节点时间段的子段，所以求子树苹果数，只需求数组某区间的和即可。用树状数组比较快。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

#define maxn  200005

struct sedge
{
	int v, next;
}edge[maxn];

struct sfork
{
	int s, e;
}fork[maxn];

int edgenum, head[maxn], xtime, ar[maxn * 2], apple[maxn], N;

void addedge(int a, int b)
{
	edge[edgenum].v = b;
	edge[edgenum].next = head[a];
	head[a] = edgenum;
	edgenum++;
}

void dfs(int a)
{
	fork[a].s = xtime;
	xtime++;
	for (int i = head[a]; i != -1; i = edge[i].next)
			dfs(edge[i].v);
	fork[a].e = xtime;
	xtime++;
}

int lowbit(int t)
{
	return t &(-t);
}

void add(int i, int v)
{
	for (; i < N; ar[i] += v, i += lowbit(i));
}

int sum(int i)
{
	int s = 0;
	for (; i > 0; s += ar[i], i-=lowbit(i));
	return s;
}
int main()
{
	//freopen("D:\\t.txt", "r", stdin);
	edgenum = 0;
	xtime = 1;
	memset(head, -1, sizeof(head));
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		addedge(a, b);
	}
	dfs(1);
	memset(ar, 0, sizeof(ar));
	N = n * 2;
	for (int i = 1; i <= N; i++)
		ar[i] = (i) - (i - lowbit(i));
	for (int i = 1; i <= n; i++)
		apple[i] = 1;
	int q;
	scanf("%d", &q);
	getchar();
	for (int i = 0; i < q; i++)
	{
		char ch;
		int num;
		scanf("%c%d", &ch, &num);
		getchar();
		if (ch == 'C')
		{
			int temp;
			if (apple[num] == 1)
				temp = -1;
			else
				temp = 1;
			add(fork[num].s, temp);
			add(fork[num].e, temp);
			apple[num] += temp;
		}
		else
			printf("%d\n", (sum(fork[num].e) - sum(fork[num].s))/2 + apple[num]);
	}
	return 0;
}