DeepSeek LeetCode 3624. 位计数深度为 K 的整数数目 II Java实现

这道题需要支持两种操作区间查询和单点更新数据规模达到 1e5所以高效的动态数据结构是关键。综合来看官方题解推荐的多棵线段树或树状数组的方案实现清晰、性能优秀。以下是基于树状数组Fenwick Tree的完整 Java 实现。核心思路1. 理解深度对于任意正整数 xdepth(x) 0若 x1否则 depth(x) 1 depth(popcount(x))。因为约束里 k 5我们只需关注深度 0 到 5。2. 数据结构设计创建 6 个树状数组 bit[0] 到 bit[5]。bit[d] 维护一个 0/1 数组其中 1 表示该位置元素的深度正好是 d。3. 查询与更新· 查询对 depth k 的树状数组直接计算 [l, r] 区间和。· 更新计算新旧元素的深度在对应的两个树状数组上分别执行 -1 和 1 的更新操作。Java 代码实现javaclass Solution {private static final int MAX_K 6; // k 的范围是 0 到 5public int[] popcountDepth(long[] nums, long[][] queries) {int n nums.length;// 预计算深度数组int[] depth new int[n];for (int i 0; i n; i) {depth[i] computeDepth(nums[i]);}// 初始化 6 棵树状数组FenwickTree[] bits new FenwickTree[MAX_K];for (int i 0; i MAX_K; i) {bits[i] new FenwickTree(n);}// 根据初始深度填充树状数组for (int i 0; i n; i) {int d depth[i];if (d MAX_K) {bits[d].add(i, 1);}}// 处理查询ListInteger ansList new ArrayList();for (long[] q : queries) {int type (int) q[0];if (type 1) {int l (int) q[1], r (int) q[2], k (int) q[3];ansList.add(bits[k].rangeSum(l, r));} else { // type 2int idx (int) q[1];long newVal q[2];int oldDepth depth[idx];int newDepth computeDepth(newVal);// 只有深度变化时才更新树状数组if (oldDepth ! newDepth) {if (oldDepth MAX_K) bits[oldDepth].add(idx, -1);if (newDepth MAX_K) bits[newDepth].add(idx, 1);depth[idx] newDepth;nums[idx] newVal; // 更新原数组以便后续计算}}}// 将结果转换为 int[]int[] ans new int[ansList.size()];for (int i 0; i ansList.size(); i) {ans[i] ansList.get(i);}return ans;}// 计算一个数的位计数深度private int computeDepth(long x) {if (x 1) return 0;// 预计算 1~64 的深度加速大数的计算// depth[1]0, depth[popcount(x)] 1 depth[popcount(popcount(x))]...return 1 depthTable[Long.bitCount(x)];}// 静态预计算表private static final int[] depthTable new int[65];static {depthTable[1] 0;for (int i 2; i 64; i) {depthTable[i] 1 depthTable[Integer.bitCount(i)];}}// 树状数组实现 (0-indexed)static class FenwickTree {private final int[] tree;private final int n;public FenwickTree(int n) {this.n n;this.tree new int[n 1];}// 将索引 i 处的值增加 delta (i 是 0-based)public void add(int i, int delta) {for (int idx i 1; idx n; idx idx -idx) {tree[idx] delta;}}// 查询前缀和 [0, i] (i 是 0-based)private int prefixSum(int i) {int sum 0;for (int idx i 1; idx 0; idx - idx -idx) {sum tree[idx];}return sum;}// 查询区间和 [l, r] (l, r 是 0-based)public int rangeSum(int l, int r) {if (l r) return 0;return prefixSum(r) - (l 0 ? 0 : prefixSum(l - 1));}}}复杂度分析· 时间复杂度预处理 O(n * MAX_K)每次查询和更新 O(log n)。总复杂度 O((n m) log n)其中 m 是查询总数。· 空间复杂度O(n * MAX_K)这里 MAX_K 是常数 6所以是 O(n)。这个解法利用树状数组在支持点更新和区间查询上的优势能够高效地处理大规模动态数据。