二叉索引树（Fenwick Tree）原理与实现

一、问题描述
二叉索引树（Fenwick Tree），又称树状数组，是一种高效处理动态前缀和查询与单点更新的数据结构。传统数组计算前缀和需要O(n)时间，单点更新后重新计算前缀和需要O(n)时间。Fenwick Tree通过巧妙的二进制索引设计，将前缀和查询和单点更新时间复杂度均优化至O(log n)。

二、核心思想

1. 二进制索引规律：每个整数索引i的二进制表示中，最低位的1（Lowest Set Bit, LSB）决定该位置管辖的区间范围。
   • 例如：索引6(二进制110)的LSB是2（第二位），管辖区间长度为2，即[5,6]。
2. 管辖关系：位置i存储的不是单个元素值，而是原数组中区间[i-LSB(i)+1, i]的和。

三、数据结构构建

1. 基础数组：使用长度为n+1的数组tree（索引1到n），初始化为0。
2. LSB计算：通过位运算i & (-i)快速获取最低位1的数值。
   • 例如：6 & (-6) = 2（二进制110 & 010 = 010）

四、关键操作详解

1. 单点更新（update）：

   • 操作：在位置i增加差值delta
   • 步骤：
     a. 从索引i开始，将delta加到tree[i]
     b. 令i = i + LSB(i)，更新下一个管辖包含i的位置
     c. 重复直到i>n
   • 示例：在n=8的树中更新位置5（二进制101）：
     • 步骤1：更新tree[5]（管辖[5,5]）
     • 步骤2：i=5+1=6（二进制110），更新tree[6]（管辖[5,6]）
     • 步骤3：i=6+2=8（二进制1000），更新tree[8]（管辖[1,8]）
     • 步骤4：i=8+8=16>8，终止

2. 前缀和查询（query）：

   • 操作：查询区间[1,i]的和
   • 步骤：
     a. 从索引i开始，累加tree[i]到结果
     b. 令i = i - LSB(i)，跳转到前一个管辖区间
     c. 重复直到i=0
   • 示例：查询i=7（二进制111）的前缀和：
     • 步骤1：累加tree[7]（管辖[7,7]）
     • 步骤2：i=7-1=6（二进制110），累加tree[6]（管辖[5,6]）
     • 步骤3：i=6-2=4（二进制100），累加tree[4]（管辖[1,4]）
     • 步骤4：i=4-4=0，终止

五、区间和查询扩展
查询区间[l, r]的和可通过两次前缀和操作实现：query(r) - query(l-1)

• 示例：查询[3,6]的和 = query(6) - query(2)

六、复杂度分析

• 更新时间：O(log n)（每次更新沿二进制位向上跳转）
• 查询时间：O(log n)（每次查询沿二进制位向下跳转）
• 空间复杂度：O(n)

七、应用场景

1. 频繁更新的动态前缀和计算
2. 逆序对计数（配合坐标离散化）
3. 代替线段树处理单点更新+区间查询问题

八、代码实现（Python示例）

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i  # 跳转到父节点
    
    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i  # 跳转到前一个区间
        return s
    
    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

九、对比线段树

• 优势：代码简洁、常数因子小、空间占用少
• 劣势：不支持区间更新、复杂区间操作（需结合差分技巧扩展）