题目内容

塔子哥是一个热爱编程的大学生，他喜欢参加各种算法竞赛，挑战自己的智力。有一天，他在网上看到了一个有趣的二叉树问题，他决定尝试一下。他用纸和笔画出了一个 $n$ 层的满二叉树（共 $2^n-1$ 个节点，编号从 $1$ 到 $2^n-1$ ，对于编号为 $i$ （ $1 \le i\le 2^{n-1} -1$ ）的节点，它的左儿子为 $2*i$ ，它的右儿子为 $2*i+1$），然后用红色的笔操作 $q$ 次，每次都是在某些节点上画圈，表示将这些节点及其子树染红。他想知道每次染红后，二叉树中有多少个红色的节点。

他觉得这个问题很简单，只要用递归或者栈就可以解决。但是，当他开始编写代码时，他发现问题并没有那么容易。他需要考虑很多细节，比如如何存储和更新二叉树的状态，如何避免重复计算，如何优化时间和空间复杂度等等。他越写越觉得头疼，越写越觉得不对劲。他开始怀疑自己的能力，甚至怀疑这个问题是否有解。他不甘心放弃，他决定向你求助，希望你能给他一些提示或者思路。你能帮助塔子哥吗？

思路

维护红色节点的个数，需要维护二叉树中的每条链之间的影响， 影响分为两部分，第一部分是从上到下的影响，还是比如把9的子树涂红，之后再图9的子树中的节点比如18、19、36、72......等都不应该计算，这部分用一个哈希表存下之前出现过的所有点，再遍历当前节点的所有祖先，如果在表中出现了，就不计算当前节点了，因为祖先节点的个数是优先的，为 $log_2a_i$ 个，所以时间复杂度很低。

还有从下到上的影响，比如说将9的子树涂红之后，下次涂9的父节点4的时候就要少计算一部分，包括4的父节点2，2的父节点1都要少算一部分，这部分用一个哈希表存储所有的影响，同样因为祖先数很少，所以访问的节点数不多，可以保证时间复杂度。

计算子树中节点数量时先计算当前节点的子树的深度，就是总深度n减去当前节点的深度，从当前节点遍历到根节点即可，二叉树的节点数量为 $1+2+4+...+2^n = 2^{n-1}-1$。