Readme

3624.Number-of-Integers-With-Popcount-Depth-Equal-to-K-II

首先我们要意识到，任何一个长整型的popcount depth不可能很大。

首先对于<=64的数，我们可以使用穷举的方法，发现最坏情况就是63，它的路径就是63->6->2->1。而剩下任意大于64的长整型（共有64个bit），它的第一步变化之后必然落入[1,64]之间。由之前的结论，其路径最多再走3步就会到1。所以结论是：任意一个长整型，其popcount depth不超过4.

既然处理任何一个数只需要4步就能求出深度，那我们可以将所有nums都先处理一遍，将所有nums可以按照depth分类。于是对于每一种深度，我们可以知道有哪些数对应，将其index标记为1（否则标记为0），这样用树状数组就可以高效（log的时间）地算出任意区间内有多少数对应该深度（即求区间和），满足了第一类query的要求。同时树状数组支持对单点的动态修改，支持了第二类query的操作。

因为深度的种类只有5种，我们只需要开5个这样的树状数组，因此空间复杂度也是符合要求的。