树状数组

题意：一个树，以树枝连接两个点的形式给出，固定以1为整棵树的根。苹果长在树的节点上，节点上只可能0或1个苹果，一开始每个节点都有1个苹果

有两种操作，C表示更改某个节点的苹果数，0变1,1变0。Q表示查询，某个节点（包括）的子树上一共有多少个苹果

这题是选拔赛时候的题，一看，单点修改，区间查询？线段树？后来一直没想出来，今天看解题报告才明白真的是，不过是树状数组（不过按照理论来将，凡是树状数组能解决的问题，线段树都可以解决，反之不然）。整个问题最难的时候怎么映射成树状数组，映射后，只是树状数组的模板操作

 

1.首先数据太大，不用显式建树，只是用vector来保存边的信息，仅仅是利用vector来遍历二叉树，而且是后序遍历

2.

后序遍历二叉树，并按照遍历顺序重新给节点标号，那么有几个较为容易理解的结论

1.根节点的标号一定比所有子孙后代节点的标号大

2.但是标号比根节点小的节点不一定是根节点的子孙后代

3.根节点的子孙后代一定是和根节点的标号是连着的，根节点的标号为a，子孙后代节点标号范围在[b,a-1]，是一段连续的区间

上面这3点比较容易想到，基于上面这3点，我们不难提出一个问题，怎么确定哪些标号是根节点的子孙后代呢？即第3条结论的b要怎么确定呢？

用时间戳来记录，或者说简单点就是访问的顺序（或说）深度来表示

起始时间为0，每访问到一个节点其实就是花费了一个时间，记录下第1次访问到该节点的时间。另外，当最后一次回到该节点时（即访问完所有的子孙后代），

记录一下时间，其实也就是后序遍历时给这个节点标号，这两步是同时进行的。

那么我们就可以知道了一个节点第一次被访问的时间，和最后离开该节点的时间，这两个时间相减得到一个时间差，在这段时间里我们只做了什么？

没错，就是访问了该节点的子孙后代！所有，标号在该差值范围内的节点就是该节点的子孙后代

所以查询的时候，我们要的不是前缀和，只是要区间和，而区间和可以由两个前缀和相减所得

sum[num[u]] - sum[num[u]-x'-1] ,x'=last[u]-first[u]

 

今天很累不想说了，剩下的看代码吧，应该能看懂的。。。。

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 100010int time,ccount;bool vis[N]; //dfs的标记数组bool app[N]; //每个点是否有苹果typedef vector
        
          INF;vector
         
           e(N);int first[N],last[N],num[N]; //第一次访问和离开一个节点的时间，后序遍历该节点的编号int C[N]; //映射后的树状数组int lowbit(int x){    return x&(-x);}void init(int n){    for(int i=0; i<=n; i++)    {        app[i]=true;        C[i]=lowbit(i); //因为一开每个点都有1个苹果所以可以初始化不用沿路径更新    }}void build(int n){    for(int i=1; i