3624. 具有相等popcount深度K的整数数量 II

Hard

题目描述

给你一个整数数组 nums。

对于任何正整数 x，定义以下序列：

p₀ = x
pᵢ₊₁ = popcount(pᵢ)，对于所有 i ≥ 0，其中 popcount(y) 是 y 的二进制表示中设置位（1的个数）的数量。

这个序列最终会到达值 1。

x 的 popcount深度定义为最小的整数 d ≥ 0，使得 pₑ = 1。

例如，如果 x = 7（二进制表示为 “111”），那么序列是：7 → 3 → 2 → 1，所以 7 的 popcount深度是 3。

你还会得到一个二维整数数组 queries，其中每个 queries[i] 是以下之一：

[1, l, r, k] - 确定满足 l ≤ j ≤ r 且 nums[j] 的 popcount深度等于 k 的索引 j 的数量。
[2, idx, val] - 将 nums[idx] 更新为 val。

返回一个整数数组 answer，其中 answer[i] 是第 i 个类型 [1, l, r, k] 查询的索引数量。

示例 1：

输入：nums = [2,4], queries = [[1,0,1,1],[2,1,1],[1,0,1,0]]
输出：[2,1]

示例 2：

输入：nums = [3,5,6], queries = [[1,0,2,2],[2,1,4],[1,1,2,1],[1,0,1,0]]
输出：[3,1,0]

示例 3：

输入：nums = [1,2], queries = [[1,0,1,1],[2,0,3],[1,0,0,1],[1,0,0,2]]
输出：[1,0,1]

约束：

1 ≤ n == nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10¹⁵
1 ≤ queries.length ≤ 10⁵
queries[i].length == 3 或 4
queries[i] == [1, l, r, k] 或 queries[i] == [2, idx, val]
0 ≤ l ≤ r ≤ n - 1
0 ≤ k ≤ 5
0 ≤ idx ≤ n - 1
1 ≤ val ≤ 10¹⁵

解题思路

这道题需要处理两种操作：区间查询和单点更新。关键在于高效地维护每个数字的popcount深度信息。

核心思路：

预计算深度：对于每个数字，计算其popcount深度。由于约束k ≤ 5，深度最大也不会超过5。
树状数组维护：使用6个树状数组（深度0到5），每个树状数组记录对应深度的数字位置。
处理查询：
- 更新操作：从旧深度的树状数组中删除，在新深度的树状数组中添加
- 查询操作：在对应深度的树状数组中查询区间和

算法步骤：

实现popcount深度计算函数
初始化6个树状数组，为每个数字在对应深度的树状数组中设置标记
对于更新操作，更新对应位置的深度信息
对于查询操作，返回指定深度树状数组在给定区间的和

时间复杂度分析：

预处理：O(n log max_val)，计算所有数字的深度
每次查询/更新：O(log n)
总时间复杂度：O(n log max_val + q log n)

这种方法充分利用了深度范围小（≤5）的特点，通过空间换时间实现了高效的区间查询和单点更新。

代码实现

class Solution {
    class FenwickTree {
        vector<int> tree;
        int n;
        
    public:
        FenwickTree(int size) : n(size), tree(size + 1, 0) {}
        
        void update(int idx, int delta) {
            for (int i = idx + 1; i <= n; i += i & (-i)) {
                tree[i] += delta;
            }
        }
        
        int query(int idx) {
            if (idx < 0) return 0;
            int sum = 0;
            for (int i = idx + 1; i > 0; i -= i & (-i)) {
                sum += tree[i];
            }
            return sum;
        }
        
        int rangeQuery(int l, int r) {
            return query(r) - query(l - 1);
        }
    };
    
    int calculateDepth(long long x) {
        int depth = 0;
        while (x != 1) {
            x = __builtin_popcountll(x);
            depth++;
        }
        return depth;
    }
    
public:
    vector<int> popcountDepth(vector<long long>& nums, vector<vector<long long>>& queries) {
        int n = nums.size();
        vector<int> depths(n);
        vector<FenwickTree> fenwick(6, FenwickTree(n));
        
        // 预计算深度并初始化树状数组
        for (int i = 0; i < n; i++) {
            depths[i] = calculateDepth(nums[i]);
            fenwick[depths[i]].update(i, 1);
        }
        
        vector<int> result;
        
        for (const auto& query : queries) {
            if (query[0] == 1) {
                // 查询操作 [1, l, r, k]
                int l = query[1], r = query[2], k = query[3];
                result.push_back(fenwick[k].rangeQuery(l, r));
            } else {
                // 更新操作 [2, idx, val]
                int idx = query[1];
                long long val = query[2];
                
                // 从旧深度中移除
                fenwick[depths[idx]].update(idx, -1);
                
                // 计算新深度并添加
                depths[idx] = calculateDepth(val);
                fenwick[depths[idx]].update(idx, 1);
                
                nums[idx] = val;
            }
        }
        
        return result;
    }
};

class Solution:
    def popcountDepth(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        class FenwickTree:
            def __init__(self, n):
                self.n = n
                self.tree = [0] * (n + 1)
            
            def update(self, idx, delta):
                idx += 1
                while idx <= self.n:
                    self.tree[idx] += delta
                    idx += idx & (-idx)
            
            def query(self, idx):
                if idx < 0:
                    return 0
                idx += 1
                result = 0
                while idx > 0:
                    result += self.tree[idx]
                    idx -= idx & (-idx)
                return result
            
            def range_query(self, l, r):
                return self.query(r) - self.query(l - 1)
        
        def calculate_depth(x):
            depth = 0
            while x != 1:
                x = bin(x).count('1')
                depth += 1
            return depth
        
        n = len(nums)
        depths = [calculate_depth(num) for num in nums]
        fenwick = [FenwickTree(n) for _ in range(6)]
        
        # 初始化树状数组
        for i in range(n):
            fenwick[depths[i]].update(i, 1)
        
        result = []
        
        for query in queries:
            if query[0] == 1:
                # 查询操作 [1, l, r, k]
                l, r, k = query[1], query[2], query[3]
                result.append(fenwick[k].range_query(l, r))
            else:
                # 更新操作 [2, idx, val]
                idx, val = query[1], query[2]
                
                # 从旧深度中移除
                fenwick[depths[idx]].update(idx, -1)
                
                # 计算新深度并添加
                depths[idx] = calculate_depth(val)
                fenwick[depths[idx]].update(idx, 1)
                
                nums[idx] = val
        
        return result

public class Solution {
    public class FenwickTree {
        private int[] tree;
        private int n;
        
        public FenwickTree(int size) {
            n = size;
            tree = new int[size + 1];
        }
        
        public void Update(int idx, int delta) {
            for (int i = idx + 1; i <= n; i += i & (-i)) {
                tree[i] += delta;
            }
        }
        
        public int Query(int idx) {
            if (idx < 0) return 0;
            int sum = 0;
            for (int i = idx + 1; i > 0; i -= i & (-i)) {
                sum += tree[i];
            }
            return sum;
        }
        
        public int RangeQuery(int l, int r) {
            return Query(r) - Query(l - 1);
        }
    }
    
    private int CalculateDepth(long x) {
        int depth = 0;
        while (x != 1) {
            x = (long)System.Numerics.BitOperations.PopCount((ulong)x);
            depth++;
        }
        return depth;
    }
    
    public int[] PopcountDepth(long[] nums, long[][] queries) {
        int n = nums.Length;
        int[] depths = new int[n];
        FenwickTree[] fenwick = new FenwickTree[6];
        
        for (int i = 0; i < 6; i++) {
            fenwick[i] = new FenwickTree(n);
        }
        
        // 预计算深度并初始化树状数组
        for (int i = 0; i < n; i++) {
            depths[i] = CalculateDepth(nums[i]);
            fenwick[depths[i]].Update(i, 1);
        }
        
        List<int> result = new List<int>();
        
        foreach (var query in queries) {
            if (query[0] == 1) {
                // 查询操作 [1, l, r, k]
                int l = (int)query[1], r = (int)query[2], k = (int)query[3];
                result.Add(fenwick[k].RangeQuery(l, r));
            } else {
                // 更新操作 [2, idx, val]
                int idx = (int)query[1];
                long val = query[2];
                
                // 从旧深度中移除
                fenwick[depths[idx]].Update(idx, -1);
                
                // 计算新深度并添加
                depths[idx] = CalculateDepth(val);
                fenwick[depths[idx]].Update(idx, 1);
                
                nums[idx] = val;
            }
        }
        
        return result.ToArray();
    }
}

var popcountDepth = function(nums, queries) {
    class FenwickTree {
        constructor(n) {
            this.n = n;
            this.tree = new Array(n + 1).fill(0);
        }
        
        update(idx, delta) {
            idx += 1;
            while (idx <= this.n) {
                this.tree[idx] += delta;
                idx += idx & (-idx);
            }
        }
        
        query(idx) {
            if (idx < 0) return 0;
            idx += 1;
            let sum = 0;
            while (idx > 0) {
                sum += this.tree[idx];
                idx -= idx & (-idx);
            }
            return sum;
        }
        
        rangeQuery(l, r) {
            return this.query(r) - this.query(l - 1);
        }
    }
    
    function calculateDepth(x) {
        let depth = 0;
        while (x !== 1) {
            x = x.toString(2).split('1').length - 1;
            depth++;
        }
        return depth;
    }
    
    const n = nums.length;
    const depths = nums.map(calculateDepth);
    const fenwick = Array.from({length: 6}, () => new FenwickTree(n));
    
    // 初始化树状数组
    for (let i = 0; i < n; i++) {
        fenwick[depths[i]].update(i, 1);
    }
    
    const result = [];
    
    for (const query of queries) {
        if (query[0]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
预处理	O(n log max_val)	O(n)
单次查询	O(log n)	O(1)
单次更新	O(log n)	O(1)
总体	O(n log max_val + q log n)	O(n)

其中 n 是数组长度，q 是查询数量，max_val 是数组中的最大值。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析