doocs/leetcode 树状数组技巧：高效解决区间查询与单点更新问题

技术文档

doocs/leetcode 树状 数组技巧：高效解决区间查询与单点更新问题

【免费下载链接】leetcode 🔥LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解项目地址: https://gitcode.com/doocs/leetcode

引言

在算法竞赛和实际开发中，我们经常需要处理区间查询和单点更新的问题。传统的暴力方法在数据量较大时效率极低，时间复杂度为 O(n)。树状数组（Fenwick Tree/Binary Indexed Tree）作为一种高效的数据结构，能够在 O(log n) 的时间复杂度内完成这两种操作，是解决这类问题的利器。

本文将深入解析树状数组的核心原理、实现技巧，并通过 doocs/leetcode 中的实际案例展示其强大威力。

什么是树状数组？

树状数组（Fenwick Tree），也称为二叉索引树（Binary Indexed Tree），是由 Peter M. Fenwick 在 1994 年提出的一种数据结构。它主要用于高效处理以下两种操作：

单点更新：将指定位置的数值加上一个增量
前缀和查询：查询从起始位置到指定位置的所有元素之和

核心思想

树状数组的核心思想是利用二进制表示的特性，通过巧妙的索引设计来存储部分和，从而在更新和查询时只需要操作 log(n) 个节点。

mermaid

树状数组的实现原理

关键操作：lowbit

树状数组的核心是 lowbit 函数，它返回一个数二进制表示中最低位的 1 所对应的值。

def lowbit(x: int) -> int: return x & -x

例如：

lowbit(6) = 2 （6 的二进制是 110，最低位的 1 对应 2）
lowbit(8) = 8 （8 的二进制是 1000，最低位的 1 对应 8）

基本操作实现

1. 更新操作

def update(self, x: int, delta: int): while x <= self.n: self.c[x] += delta x += x & -x # 移动到父节点

2. 查询操作

def query(self, x: int) -> int: s = 0 while x > 0: s += self.c[x] x -= x & -x # 移动到前一个区间 return s

实战应用：LeetCode 307题解析

问题描述

实现一个支持区间和查询与单点更新的数据结构：

NumArray(int[] nums)：用整数数组初始化对象
void update(int index, int val)：将 nums[index] 的值更新为 val
int sumRange(int left, int right)：返回 nums[left] + nums[left+1] + ... + nums[right]

树状数组解决方案

class BinaryIndexedTree: __slots__ = [\"n\", \"c\"] def __init__(self, n): self.n = n self.c = [0] * (n + 1) def update(self, x: int, delta: int): while x  int: s = 0 while x > 0: s += self.c[x] x -= x & -x return sclass NumArray: __slots__ = [\"tree\"] def __init__(self, nums: List[int]): self.tree = BinaryIndexedTree(len(nums)) for i, v in enumerate(nums, 1): self.tree.update(i, v) def update(self, index: int, val: int) -> None: prev = self.sumRange(index, index) self.tree.update(index + 1, val - prev) def sumRange(self, left: int, right: int) -> int: return self.tree.query(right + 1) - self.tree.query(left)

复杂度分析

操作时间复杂度空间复杂度初始化 O(n log n) O(n) 单点更新 O(log n) O(1) 区间查询 O(log n) O(1)

树状数组的进阶应用

1. 逆序对计数

树状数组可以高效计算数组中的逆序对数量：

def count_inversions(nums): # 离散化处理 sorted_nums = sorted(set(nums)) mapping = {v: i+1 for i, v in enumerate(sorted_nums)} bit = BinaryIndexedTree(len(sorted_nums)) count = 0 for num in reversed(nums): pos = mapping[num] count += bit.query(pos - 1) bit.update(pos, 1) return count

2. 二维树状数组

对于二维矩阵的区间查询，可以扩展为二维树状数组：

class BinaryIndexedTree2D: def __init__(self, m, n): self.m = m self.n = n self.c = [[0] * (n + 1) for _ in range(m + 1)] def update(self, x, y, delta): i = x while i <= self.m: j = y while j  0: j = y while j > 0: res += self.c[i][j] j -= j & -j i -= i & -i return res

树状数组 vs 线段树

特性树状数组线段树代码复杂度简单复杂空间复杂度 O(n) O(4n) 单点更新 O(log n) O(log n) 区间查询 O(log n) O(log n) 区间更新不支持支持功能丰富性有限丰富

mermaid

常见问题与解决方案

Q1: 为什么树状数组的索引从1开始？

A: 因为 lowbit(0) = 0，会导致无限循环。从1开始可以避免这个问题。

Q2: 如何处理负数或浮点数？

A: 需要进行离散化处理，将原始值映射到正整数索引。

Q3: 什么时候选择树状数组而不是线段树？

A: 当只需要单点更新和前缀和查询，且代码简洁性更重要时。

性能优化技巧

使用 __slots__：减少内存占用，提高访问速度
批量初始化：避免多次调用 update，可以优化初始化过程
缓存查询结果：对于重复查询可以缓存结果
使用位运算：充分利用 Python 的位运算优化

总结

树状数组是一种极其高效的数据结构，特别适合处理单点更新和前缀和查询问题。通过本文的详细解析和实战案例，相信你已经掌握了树状数组的核心原理和应用技巧。

关键收获：

理解 lowbit 函数的原理和作用
掌握树状数组的更新和查询操作
学会在实际问题中应用树状数组
了解树状数组与线段树的区别和选择策略

树状数组虽然功能相对有限，但在适合的场景下，其简洁性和高效性使其成为算法竞赛和工程开发中的宝贵工具。

点赞/收藏/关注三连，获取更多算法干货！下期我们将深入探讨线段树的高级应用技巧。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

doocs/leetcode 树状数组技巧：高效解决区间查询与单点更新问题