Binary Indexed Tree

定义 Definition

Binary Indexed Tree（也常称 Fenwick Tree，树状数组）是一种用于高效处理前缀和查询与单点更新的数据结构，常见于算法与竞赛编程中。典型时间复杂度为：查询与更新均为 **O(log n)**。它主要适用于可用“加法/减法”等可逆运算维护的区间信息（如和、计数、频率等）。

例句 Examples

I use a binary indexed tree to maintain prefix sums in an array.
我用树状数组来维护数组的前缀和。

With a binary indexed tree, we can update one element and query the sum of the first k elements in logarithmic time.
使用树状数组，我们可以在对数时间内完成单点更新，并查询前 k 个元素的总和。

发音 Pronunciation (IPA)

/ˈbaɪnəri ˈɪndɛkst triː/

词源 Etymology

“Binary indexed tree”直译为“二进制索引树”：它利用下标的二进制表示来决定每个节点负责的区间长度（常见操作是取最低位的 1，即 lowbit），从而把数组信息按层级分块存储与累计。该结构与 Peter Fenwick 在 1994 年提出的相关方法紧密关联，因此也常被称为 Fenwick Tree。

相关词 Related Words

• Fenwick
• Prefix
• Cumulative
• Frequency
• Update
• Query
• Segment
• Segment Tree
• Range
• Logarithmic

文学与著作中的用例 Literary Works

• 《Competitive Programming》（Steven Halim 等）：在“数据结构/区间查询”相关章节中常介绍 Binary Indexed Tree/Fenwick Tree 的用法与代码模板。
• 《CP3: Competitive Programming 3》（Steven Halim 等）：以竞赛题型为背景讲解前缀和与 Fenwick Tree 的典型应用。
• 《The Algorithm Design Manual》（Steven S. Skiena）：在讨论常用数据结构与查询/更新权衡时，常提及 Fenwick Tree 作为实用结构之一。