树状数组：单点更新区间查询的终极利器——从原理到实战的完整指南

树状数组：单点更新区间查询的终极利器——从原理到实战的完整指南

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

树状数组（Fenwick Tree）是一种高效的数据结构，专为单点更新和区间查询操作设计，时间复杂度均为O(logN)。在处理动态数组的前缀和、逆序数统计等场景时，它比前缀和数组和线段树更具优势，尤其适合需要频繁更新和查询的场景。本文将带你深入理解树状数组的核心原理、实现方法及实战应用，帮助你轻松掌握这一算法利器！

一、树状数组核心概念解析

1.1 为什么需要树状数组？

传统数组在处理前缀和查询时需要O(N)时间，而单点更新仅需O(1)。但当面临频繁的更新与查询交替操作时，这种效率就显得不足。例如：

• 统计数组中任意区间的和（如sum(1..5)）
• 动态修改数组元素后快速查询前缀和
• 计算逆序数、频率统计等高级问题

树状数组通过巧妙的二进制分解思想，将这两种操作的时间复杂度都优化到O(logN)，完美平衡了效率与实现复杂度。

1.2 树状数组的结构与原理

树状数组的核心是父子节点索引的二进制关系。每个节点i的父节点为i + (i & -i)，子节点为i - (i & -i)。这种结构使得每个节点负责存储特定区间的和，例如：

• 节点1（二进制0001）覆盖区间[1,1]
• 节点2（二进制0010）覆盖区间[1,2]
• 节点3（二进制0011）覆盖区间[3,3]
• 节点4（二进制0100）覆盖区间[1,4]

树状数组的层级结构与区间覆盖关系（树状数组结构示意图）

二、树状数组的核心操作实现

2.1 单点更新（Update）

更新操作通过向上传递实现，将变化值逐层累加到父节点：

def update(self, index, delta): # index 从1开始 while index <= self.size: self.tree[index] += delta index += index & -index

2.2 前缀和查询（Query）

查询操作通过向下分解实现，累加覆盖目标区间的节点值：

def query(self, index): # 查询[1..index]的和 res = 0 while index > 0: res += self.tree[index] index -= index & -index return res

2.3 区间和查询（Range Query）

利用前缀和相减得到任意区间[l..r]的和：

def range_query(self, l, r): return self.query(r) - self.query(l-1)

三、实战应用：从逆序数到频率统计

3.1 逆序数统计（LeetCode 493. 翻转对）

树状数组可高效解决逆序数问题。以"翻转对"为例（i < j且nums[i] > 2*nums[j]），核心思路是：

1. 对数组元素进行离散化（处理大数问题）
2. 从后向前遍历，查询小于当前元素一半的数量
3. 将当前元素插入树状数组

# 核心统计逻辑（完整代码见problems/493.reverse-pairs.md） def reversePairs(self, nums): # 离散化处理 sorted_nums = sorted(set(nums + [2*x for x in nums])) rank = {v:i+1 for i,v in enumerate(sorted_nums)} # 1-based索引 ft = FenwickTree(len(sorted_nums)) res = 0 for num in reversed(nums): # 查询小于num/2的元素数量 target = num / 2 idx = bisect.bisect_left(sorted_nums, target) res += ft.query(idx) # 插入当前元素 ft.update(rank[num], 1) return res

3.2 动态频率统计

在需要实时统计元素出现次数的场景（如数据流中的TOP K问题），树状数组可替代哈希表实现O(logN)级别的更新与查询：

# 统计元素x的出现次数 def count_freq(x): return ft.query(rank[x]) - ft.query(rank[x]-1)

四、树状数组 vs 其他数据结构

树状数组以极简的实现和高效的性能，成为处理动态前缀和问题的首选。

五、学习资源与进阶练习

5.1 推荐学习路径

1. 基础实现：掌握树状数组的构造、更新、查询操作
2. 离散化技巧：处理大数问题（如坐标压缩）
3. 经典问题：逆序数、区间和、频率统计
4. 扩展应用：二维树状数组、树状数组与线段树结合

5.2 实战练习题目

• LeetCode 315. 计算右侧小于当前元素的个数
• LeetCode 493. 翻转对
• LeetCode 307. 区域和检索 - 数组可修改

六、总结

树状数组通过二进制分解的巧妙设计，实现了O(logN)的单点更新和区间查询，是处理动态数组问题的高效工具。它的核心优势在于：

• 高效性：远超前缀和数组的更新效率
• 简洁性：代码量仅需20行左右，易于实现和调试
• 灵活性：可扩展到二维问题、频率统计等多种场景

掌握树状数组，能让你在处理数组类问题时如虎添翼，轻松应对各类算法挑战！

本文代码实现及更多示例可参考项目中的thinkings/binary-search-2.md和problems/493.reverse-pairs.md。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode