当前位置：首页 > news >正文

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

news 2026/5/5 13:28:56

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

【免费下载链接】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]），核心思路是：

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

# 核心统计逻辑（完整代码见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 其他数据结构

数据结构	单点更新	区间查询	实现复杂度	适用场景
前缀和数组	O(N)	O(1)	简单	静态数组查询
树状数组	O(logN)	O(logN)	中等	动态数组、前缀和、逆序数
线段树	O(logN)	O(logN)	复杂	区间更新、复杂区间操作