POJ - 3321 Apple Tree（树状数组）

书史足自悦，安用勤与劬。这篇文章主要讲述POJ - 3321 Apple Tree（树状数组）相关的知识，希望能为你提供帮助。
原题链接
题意：
给你一个n个节点的树，每个节点上一开始都有一个苹果，现在有两种操作：
Q x ：查询 x 节点以及它的子树上一共有多少苹果；
C x ：若 x 节点上没有苹果，则增加一个，反之，则减少一个；
思路：
这是一个区间查询，单点修改的问题，我们就会想到用树状数组来做，但是怎么去维护树上的区间又是一个问题；
于是想到了用 dfs序，记录每一个节点的 left 和 right 也就转化成了区间问题；

1 /* 2 * @Author: windystreet 3 * @Date:2018-08-02 22:10:44 4 * @Last Modified by:windystreet 5 * @Last Modified time: 2018-08-02 22:56:03 6 */ 7 #include< stdio.h> 8 #include< string.h> 9 #include< algorithm> 10 #include< vector> 11 12 using namespace std; 13 14 #define X first 15 #define Y second 16 #define eps1e-2 17 #define gcd __gcd 18 #define pb push_back 19 #define PI acos(-1.0) 20 #define lowbit(x) (x)& (-x) 21 #define bug printf("!!!!! "); 22 #define mem(x,y) memset(x,y,sizeof(x)) 23 24 typedef long long LL; 25 typedef long double LD; 26 typedef pair< int,int> pii; 27 typedef unsigned long long uLL; 28 29 const int maxn = 1e5+7; 30 const LLINF= 1< < 30; 31 const int mod= 1e9+7; 32typedef vector< int> Ve; 33 vector< Ve> G(maxn); 34 int left[maxn],right[maxn],cnt=1,n; 35 int tree[maxn],vis[maxn]; 36 37 int query(int x){ 38int res = 0; 39while(x){ 40res+=tree[x]; 41x-=lowbit(x); 42} 43return res; 44 } 45 void add(int x,int v){ 46for(int i=x; i< =n; i+=lowbit(i)){ 47tree[i]+=v; 48} 49return ; 50 } 51 void dfs(int x){ 52left[x] = cnt; // 记录左端点的id 53int sz = G[x].size(); 54for(int i=0; i< sz; i++){ 55cnt++; 56dfs(G[x][i]); 57} 58right[x]=cnt; // 记录右端点的id 59 } 60 61 void solve() 62 { 63cnt = 1; 64int x,y,m; 65char op[3]; 66for(int i=0; i< =n; i++){tree[i]=0; vis[i]=1; G[i].clear(); } 67for(int i=1; i< n; i++){ 68scanf("%d%d",& x,& y); 69G[x].pb(y); // 存图 70} 71dfs(1); // dfs序 72for(int i=1; i< =n; i++){ 73add(i,1); // 每个点一开始都有一个苹果 74} 75scanf("%d",& m); 76for(int i=0; i< m; i++){ 77scanf("%s%d",op,& x); 78if(op[0]==‘Q‘){// 区间查询 79printf("%d ",query(right[x])-query(left[x]-1)); 80}else{ 81if(vis[x])add(left[x],-1); // 单点修改 82else add(left[x],1); 83vis[x]=!vis[x]; // 取反 84} 85} 86return ; 87 } 88 89 int main() 90 { 91 //freopen("in.txt","r",stdin); 92 //freopen("out.txt","w",stdout); 93 //ios::sync_with_stdio(false); 94while(scanf("%d",& n)!=EOF){ 95//printf("Case %d: ",cas++); 96solve(); 97} 98return 0; 99 }

【POJ - 3321 Apple Tree（树状数组）】