AlgorithmAndLeetCode · pull · Jul 21, 2025 · Jul 21, 2025 · Jul 21, 2025 · Jul 21, 2025
diff --git a/Readme.md b/Readme.md
@@ -378,6 +378,7 @@
 [2031.Count-Subarrays-With-More-Ones-Than-Zeros](https://github.com/wisdompeak/LeetCode/tree/master/Segment_Tree/2031.Count-Subarrays-With-More-Ones-Than-Zeros) (H)    
 [2179.Count-Good-Triplets-in-an-Array](https://github.com/wisdompeak/LeetCode/tree/master/Segment_Tree/2179.Count-Good-Triplets-in-an-Array) (H)      
 [2659.Make-Array-Empty](https://github.com/wisdompeak/LeetCode/tree/master/Segment_Tree/2659.Make-Array-Empty) (H)      
+[3624.Number-of-Integers-With-Popcount-Depth-Equal-to-K-II](https://github.com/wisdompeak/LeetCode/tree/master/Segment_Tree/3624.Number-of-Integers-With-Popcount-Depth-Equal-to-K-II) (H-)      
 
 #### [Design](https://github.com/wisdompeak/LeetCode/tree/master/Design)
 [380.Insert-Delete-GetRandom-O(1)](https://github.com/wisdompeak/LeetCode/tree/master/Design/380.Insert-Delete-GetRandom-O-1/)  (M+)   

diff --git a/...opcount-Depth-Equal-to-K-II/3624.Number-of-Integers-With-Popcount-Depth-Equal-to-K-II.cpp b/...opcount-Depth-Equal-to-K-II/3624.Number-of-Integers-With-Popcount-Depth-Equal-to-K-II.cpp
@@ -0,0 +1,88 @@
+using ll = long long;
+
+class BIT{
+    public:
+    int N;    
+    vector<long long>bitArr; // Note: all arrays are 1-index
+    vector<long long>nums;
+    long long M = 1e9+7;
+
+    void init(int N)
+    {
+        this->N = N;
+        bitArr.resize(N+1);
+        nums.resize(N+1);        
+    }
+
+    // increase nums[i] by delta
+    void updateDelta(int i, long long delta) {
+        int idx = i;
+        while (idx <= N)
+        {
+            bitArr[idx]+=delta;
+            // bitArr[idx] %= M;
+            idx+=idx&(-idx);
+        }
+    }
+
+    // sum of a range nums[1:j] inclusively
+    long long queryPreSum(int idx){
+        long long result = 0;
+        while (idx){
+            result += bitArr[idx];
+            // result %= M;
+            idx-=idx&(-idx);
+        }
+        return result;
+    }
+
+    // sum of a range nums[i:j] inclusively
+    long long sumRange(int i, int j) {    
+        return queryPreSum(j)-queryPreSum(i-1);
+    } 
+};
+
+class Solution {
+public:    
+    int getDepth(ll x) {
+        int count = 0;        
+        while (x!=1ll) {
+            x = __builtin_popcountll(x);
+            count++;            
+        }
+        return count;
+    }
+
+    vector<int> popcountDepth(vector<long long>& nums, vector<vector<long long>>& queries) {
+        int N = nums.size()+1;
+        vector<BIT> bit_arr (5);
+        for (int i=0; i<=4; i++)
+            bit_arr[i].init(N);
+
+        for (int i=0; i<nums.size(); i++) {
+            int depth = getDepth(nums[i]);
+            bit_arr[depth].updateDelta(i+1, 1);
+        }
+
+        vector<int>rets;
+        for (auto&q: queries) {
+            if (q[0]==2) {
+                ll idx = q[1], val = q[2];
+                int depth0 = getDepth(nums[idx]);
+                int depth1 = getDepth(val);
+                bit_arr[depth0].updateDelta(idx+1, -1);
+                bit_arr[depth1].updateDelta(idx+1, 1);
+                nums[idx] = val;
+            } else {
+                int l = q[1], r = q[2], k = q[3];                
+                if (k>=5)
+                    rets.push_back(0);
+                else
+                    rets.push_back(bit_arr[k].sumRange(l+1,r+1));
+            }
+        }
+
+        return rets;
+
+    }
+};
diff --git a/Segment_Tree/3624.Number-of-Integers-With-Popcount-Depth-Equal-to-K-II/Readme.md b/Segment_Tree/3624.Number-of-Integers-With-Popcount-Depth-Equal-to-K-II/Readme.md
@@ -0,0 +1,10 @@
+### 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个这样的树状数组，因此空间复杂度也是符合要求的。
+
diff --git a/Template/Bit_manipulation/Count_bit_1_numbers.cpp b/Template/Bit_manipulation/Count_bit_1_numbers.cpp
@@ -1 +1,3 @@
 __builtin_popcount(state)
+
+__builtin_popcountll(state)
Original file line number	Diff line number	Diff line change
		@@ -1 +1,3 @@
		__builtin_popcount(state)

		__builtin_popcountll(state)