苹果树 树状数组

POJ 3321 Apple Tree
每个分叉点及末梢可能有苹果（最多1个），
每次可以摘掉一个苹果，或有一个苹果新长
出来，随时查询某个分叉点往上的子树里，
一共有多少个苹果(分叉点数量： 100,000 )。
Sample Input
3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output
3
2
深度优先遍历整个苹果树，为每个节点标记
一个开始时间和结束时间（所有时间都不相
同），显然子树里面所有节点的开始和结束
时间，都位于子树树根的开始和结束时间之
间。
问题变成：
有n个节点，就有2n个开始结束时间，它们构
成序列
A 1 A 2 ….A 2n
序列里每个数是0或者1，可变化，随时查询
某个区间里数的和。当然由于苹果树上每个
放苹果的位置对应于数列里的两个数，所以
结果要除以2
树状数组
对于序列a，我们设一个数组C
C[i] = a[i – 2 k + 1] + … + a[i]
k为i在二进制下末尾0的个数
2 k 就是i 保留最右边的1，其余位全变0
i从1开始算！
C即为a的树状数组
对于i,如何求2 k ？
2 k =i &(i^(i-1)) 也就是 i&(-i)
以6为例
(6) 10 =(0110) 2
xor 6-1=(5) 10 =(0101) 2
(0011) 2
and (6) 10 = (0110) 2
(0010) 2 = (4) 10
通常我们用lowbit(x)表示x对应的2 k ,
lowbit(x) = x&(-x)
lowbit(x) 实际上就是x的二进制表示形式
留下最右边的1，其他位都变成0
C[i] = a[i-lowbit(i)+1] + …+ a[i]
C包含哪些项看上去没有规律
C1=A1
C2=A1+A2
C3=A3
C4=A1+A2+A3+A4
C5=A5
C6=A5+A6
C7=A7
C8=A1+A2+A3+A4+A5+A6+A7+A8
…………
C16=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+
A11+A12+A13+A14+A15+A16


//树状数组做
/*
一棵树上长了苹果，每一个树枝节点上有长苹果和不长苹果
两种状态，两种操作，一种操作能够改变树枝上苹果的状态，
另一种操作询问某一树枝节点以下的所有的苹果有多少。具
体做法是做一次dfs，记下每个节点的开始时间Start[i]和结
束时间End[i]，
那么对于i节点的所有子孙的开始时间和结束时间都应位于
Start[i]和End[i]之间
然后用树状数组C统计Start[i]到End[i]之间的附加苹果总数。
这里用树状数组统计区间可以用Sum(End[i])-Sum(Start[i]-1)
来计算。
*/

#include <iostream>
#include <vector>
using namespace std;
#define MY_MAX 220000
int C[MY_MAX];
typedef vector<int> VCT_INT;
vector<VCT_INT> G(MY_MAX/2); //邻接表
int Lowbit[MY_MAX];
bool HasApple[MY_MAX/2];
int Start[MY_MAX]; //dfs时的开始时间
int End[MY_MAX]; //dfs时的结束时间
int nCount = 0;
void Dfs(int v)
{
Start[v] = ++ nCount;
for( int i = 0;i < G[v].size();i ++ )
Dfs(G[v][i]);
End[v] = ++ nCount;
}
int QuerySum(int p) //求 sum(p)
{
int nSum = 0;
while( p > 0 ) {
nSum += C[p];
p -= Lowbit[p];
}
return nSum;
}
void Modify( int p,int val)
{
while( p <= nCount ) {
C[p] += val;
p += Lowbit[p];
}
}
int main()
{
int n;
scanf("%d",&n);
int x,y;
int i,j,k;
//建图
for( i = 0;i < n -1 ;i ++ ) {
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b); //a有边连到b
}
nCount = 0;
Dfs(1);
//树状数组要处理的原始数组下标范围 1 --
nCount
for( i = 1;i <= nCount;i ++) {
Lowbit[i] = i & ( i ^( i - 1));
}
for( i = 1;i <= n;i ++ )
HasApple[i] = 1;
int m;
//求C数组，即树状数组的节点的值
for( i = 1;i <= nCount;i ++ )
C[i] = i - (i - Lowbit[i]);
// C[i] = Sum[i] - Sum[i-lowbit(i)]
scanf("%d",&m);
for( i = 0;i < m;i ++ ) {
char cmd[10];
int a;
scanf("%s%d",cmd,&a);
if( cmd[0] == 'C' ) {
if( HasApple[a] ) {
Modify( Start[a],-1); Modify( End[a],-1);
HasApple[a] = 0;
}
else {
Modify( Start[a],1); Modify( End[a],1);
HasApple[a] = 1;
}
}
else {
int t1 = QuerySum(End[a]);
int t2 = QuerySum(Start[a]-1);
printf("%d\n",(t1-t2)/2 );
}
}
}

转自郭炜老师