poj 3321 Apple Tree（树状数组） - c++编程基础

辉煌北大的月赛题质量真高啊，这种树状数组真难想到。

树状数组的基本用法是区间，单点的应用，起初这个怎么都想不到如何套用到树状数组。

转化方法是将树上的节点信息查询，转为深度优先中节点顺序（代表结点编号）。进结点与出结点分别代表该结点管辖范围。

题目大意级是说，给你一颗树，最初每个节点上都有一个苹果，有两种操作：修改（即修改某一个节点，修改时这一个节点苹果从有到无，或从无到有）和查询（查询某一个节点他的子树上有多少个苹果）。

由于此题数据比较大(N<=10^5)，而且不是标准的二叉树，所以这里我们队每一个节点重新编号，另外为每一个节点赋一个左值和一个右值，表示这个节点的管辖范围。

也就是DFS搜索的时候做标记的过程，这样新的编号为1~6的节点所管辖的范围分别就是[1,6] [2,4] [3,3] [4,4] [5,6] [6,6]，其中左边的是左值，右边的是右值，节点1的区间是[1,6]，正好这棵子树有6个节点，其他也一样

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          using namespace std; #define N 100010 int n,m; int lowbit(int x){return -x&x;} void update(int *arr,int r,int num) { int i; for(i=r;i<=n;i+=lowbit(i)) arr[i]+=num; } int getsum(int *arr,int r) { int i; int ans=0; for(i=r;i>0;i-=lowbit(i)) ans+=arr[i]; return ans; } int head[N]; int next[N]; int netb[N]; int deh1[N]; int deh2[N]; int cnt,depth; int arr[N]; int a[N]; void init() { int i; //memset(a,0,sizeof(a)); memset(deh1,0,sizeof(deh1)); memset(head,-1,sizeof(head)); cnt=0;depth=0; for(i=1;i<=n;i++) update(arr,i,1),a[i]=1; } void add(int u,int v) { netb[cnt]=v;next[cnt]=head[u];head[u]=cnt++; } void dfs(int u) { deh1[u]=++depth;//代表左 int i; for(i=head[u];~i;i=next[i]) { int v=netb[i]; dfs(v); } deh2[u]=depth;//代表右 } int main() { int i,j,k,u,v,m; char str[10]; while(~scanf("%d",&n)) { init(); for(i=1;i