树状数组实战：5个LeetCode高频题解与优化技巧（附Python/Java代码）

树状数组实战5个LeetCode高频题解与优化技巧附Python/Java代码树状数组Fenwick Tree是算法面试中经常被忽视却极其高效的数据结构。不同于线段树的复杂实现树状数组以简洁的代码和优秀的常数性能著称特别适合处理动态前缀和问题。本文将聚焦LeetCode高频题目展示如何用树状数组替代传统解法显著提升算法效率。1. 树状数组核心原理与实现优化理解树状数组的关键在于掌握其二进制索引机制。与普通数组不同树状数组的每个元素并非独立存储数据而是按照特定规则维护部分区间和。这种设计使得单点更新和前缀查询都能在O(log n)时间内完成。lowbit运算是树状数组的灵魂操作它提取数字二进制表示中最低位的1def lowbit(x): return x -x在Java中实现时需注意整数溢出问题private static int lowbit(int x) { return x -x; }性能对比与朴素前缀和数组相比树状数组在动态更新场景优势明显操作类型朴素前缀和树状数组单点更新O(n)O(log n)前缀和查询O(1)O(log n)空间复杂度O(n)O(n)实际编码时树状数组有几种常见优化技巧1-based索引避免处理x0的情况批量初始化O(n)建树方法比n次add操作更快内存预分配提前确定数据范围避免扩容2. 基础应用区间和查询问题2.1 LeetCode 307. 区域和检索 - 数组可修改这是树状数组最直接的适用场景。传统解法面临两难存储原始数组查询O(n)更新O(1)存储前缀和查询O(1)更新O(n)树状数组完美平衡两者class NumArray: def __init__(self, nums: List[int]): self.n len(nums) self.tree [0] * (self.n 1) for i in range(1, self.n 1): self.tree[i] nums[i-1] j i lowbit(i) if j self.n: self.tree[j] self.tree[i] def update(self, index: int, val: int) - None: delta val - self.sumRange(index, index) i index 1 while i self.n: self.tree[i] delta i lowbit(i) def sumRange(self, left: int, right: int) - int: def query(x): res 0 while x 0: res self.tree[x] x - lowbit(x) return res return query(right 1) - query(left)复杂度分析初始化O(n)更新O(log n)查询O(log n)2.2 逆序对问题LeetCode 493. 翻转对树状数组结合离散化可以高效统计逆序对public int reversePairs(int[] nums) { // 离散化处理 SetInteger set new TreeSet(); for (int num : nums) { set.add(num); set.add(2L * num 1); } MapInteger, Integer map new HashMap(); int rank 1; for (int num : set) { map.put(num, rank); } // 树状数组统计 BIT bit new BIT(map.size()); int res 0; for (int i nums.length - 1; i 0; i--) { int key map.get(nums[i]); res bit.query(key - 1); bit.update(map.get(2L * nums[i] 1), 1); } return res; } class BIT { private int[] tree; public BIT(int size) { tree new int[size 1]; } public void update(int x, int delta) { while (x tree.length) { tree[x] delta; x x -x; } } public int query(int x) { int res 0; while (x 0) { res tree[x]; x - x -x; } return res; } }3. 进阶技巧差分数组与区间更新3.1 LeetCode 370. 区间加法树状数组结合差分思想可以高效处理区间更新class Solution: def getModifiedArray(self, length: int, updates: List[List[int]]) - List[int]: bit BIT(length 2) for start, end, inc in updates: bit.update(start 1, inc) bit.update(end 2, -inc) return [bit.query(i 1) for i in range(length)] class BIT: def __init__(self, size): self.tree [0] * (size 1) def update(self, x, delta): while x len(self.tree): self.tree[x] delta x x -x def query(self, x): res 0 while x 0: res self.tree[x] x - x -x return res3.2 LeetCode 308. 二维区域和检索 - 可变二维树状数组扩展了这种能力class NumMatrix { private int[][] tree; private int[][] nums; private int m; private int n; public NumMatrix(int[][] matrix) { if (matrix.length 0 || matrix[0].length 0) return; m matrix.length; n matrix[0].length; tree new int[m1][n1]; nums new int[m][n]; for (int i 0; i m; i) { for (int j 0; j n; j) { update(i, j, matrix[i][j]); } } } public void update(int row, int col, int val) { int delta val - nums[row][col]; nums[row][col] val; for (int i row 1; i m; i i (-i)) { for (int j col 1; j n; j j (-j)) { tree[i][j] delta; } } } public int sumRegion(int row1, int col1, int row2, int col2) { return query(row2, col2) - query(row1 - 1, col2) - query(row2, col1 - 1) query(row1 - 1, col1 - 1); } private int query(int row, int col) { int sum 0; for (int i row 1; i 0; i - i (-i)) { for (int j col 1; j 0; j - j (-j)) { sum tree[i][j]; } } return sum; } }4. 实战难题解析4.1 LeetCode 315. 计算右侧小于当前元素的个数树状数组的经典应用场景def countSmaller(nums): # 离散化处理 sorted_nums sorted(set(nums)) rank {v: i1 for i, v in enumerate(sorted_nums)} # 树状数组实现 class BIT: def __init__(self, size): self.tree [0] * (size 2) def update(self, x): while x len(self.tree): self.tree[x] 1 x x -x def query(self, x): res 0 while x 0: res self.tree[x] x - x -x return res bit BIT(len(sorted_nums)) res [] for num in reversed(nums): r rank[num] res.append(bit.query(r - 1)) bit.update(r) return res[::-1]4.2 LeetCode 1649. 通过指令创建有序数组结合树状数组统计前驱后继class Solution { public int createSortedArray(int[] instructions) { int max 0; for (int num : instructions) { max Math.max(max, num); } BIT bit new BIT(max); long cost 0; for (int i 0; i instructions.length; i) { int num instructions[i]; int less bit.query(num - 1); int greater i - bit.query(num); cost Math.min(less, greater); bit.update(num, 1); } return (int)(cost % (1e9 7)); } } class BIT { int[] tree; public BIT(int size) { tree new int[size 2]; } public void update(int x, int delta) { while (x tree.length) { tree[x] delta; x x -x; } } public int query(int x) { int sum 0; while (x 0) { sum tree[x]; x - x -x; } return sum; } }5. 性能优化与边界处理树状数组在实际应用中需要注意几个关键点离散化优化当数据范围远大于数据量时如1e9范围但只有1e5个数# 离散化示例 def discretization(nums): sorted_nums sorted(set(nums)) rank {v: i1 for i, v in enumerate(sorted_nums)} return [rank[num] for num in nums]边界条件处理索引越界检查特别是update操作负数处理需要偏移量转换大数运算使用long类型调试技巧打印树状数组内部状态对比朴素算法验证结果使用小规模测试案例在最近的算法竞赛中树状数组因其编码效率高已成为解决区间统计问题的首选方案。例如在统计动态排名、维护滑动窗口极值等场景合理运用树状数组往往能比线段树获得更优的实际运行效率。