往期链接

01 数组	02 链表	03 栈	04 队列	05 二叉树	06 二叉搜索树	07 AVL树	08 红黑树	09 B树	10 B+树

11 线段树

12 树状数组(Binary Indexed Tree / Fenwick Tree)

S1 说明

树状数组是一种可以高效处理 动态数组前缀和 的数据结构。它支持在$O(logn)$的时间复杂度内进行单点更新和区间前缀和查询。树状数组利用了数字的二进制表示，通过构建一个辅助数组，使得每个位置存储一段区间的累加信息。它通过巧妙地设计索引之间的关系，实现了高效的更新和查询操作。

树状数组的构建

树状数组以数组的形式实现，但逻辑上可以视为一棵树。对于数组$BIT[\mathrm{1...}n]：$

• 索引 $i$ 的父节点：$i+lowbit(i)$
• 索引 $i$ 的子节点：$i-lowbit(i)$

其中，$lowbit(i)$表示 $i$ 在二进制表示下最低位的1所代表的值，即 $i\&(-i)$。

复杂度

• 时间复杂度：单点更新$O(logn)$；前缀和查询$O(logn)$
• 空间复杂度 $O(n)$，需要一个额外的数组存储树状数组。

特点

• 实现简单： 树状数组的实现相对简单，易于理解和编程。
• 效率高： 在一些需要频繁更新和查询前缀和的场景下，表现出高效的性能。
• 功能专一： 相较于线段树，树状数组功能较为专一，主要用于处理前缀和问题。

应用领域

• 数组前缀和问题：快速计算数组的前缀和，支持动态更新。
• 区间求和问题：通过前缀和的差，计算任意区间的和。
• 逆序数计算：在求解数组中的逆序对数量时，利用树状数组可以高效计算。
• 算法竞赛：在各种需要动态处理前缀和的竞赛题中，树状数组是常用的数据结构。

S2 示例

python">class BinaryIndexedTree:def __init__(self, size):"""初始化树状数组:param size: 数组的大小"""self.size = sizeself.tree = [0] * (self.size + 1)  # 使用 1-based 索引def lowbit(self, x):"""计算 x 的最低位 1 所代表的值"""return x & (-x)def update(self, i, delta):"""在位置 i 增加 delta:param i: 更新的位置（1-based index）:param delta: 增加的值"""while i <= self.size:self.tree[i] += deltai += self.