题目内容

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

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