二叉索引树（Fenwick Tree） 二叉索引树（又称树状数组）是一种高效处理动态前缀和查询与单点更新的数据结构，其时间复杂度为O(log n)，空间复杂度为O(n)。下面我们分步骤讲解它的核心原理和操作。 一、问题背景 假设有一个数组arr，需要频繁执行两种操作： 单点更新：将arr[ i ]增加某个值 前缀和查询：求arr[ 0]到arr[ i ]的和 若直接使用数组，单点更新O(1)，但前缀和查询需要O(n)。Fenwick树通过巧妙的二进制索引设计，将两种操作都优化到O(log n)。 二、核心思想——低位技术（Lowbit） 定义lowbit(x)为x的二进制表示中最低位的1所对应的值，例如： lowbit(6)=2（6的二进制110，最低位1表示2） lowbit(8)=8（二进制1000） 数学上lowbit(x)=x & -x（利用补码性质） 三、树状数组的存储结构 定义树状数组tree，大小与原数组arr相同（索引从1开始更易理解） tree[ i]存储的是原数组arr中区间[ i-lowbit(i)+1, i ]的和 例如i=6（二进制110），lowbit=2，则tree[ 6]=arr[ 5]+arr[ 6 ] i=8（二进制1000），lowbit=8，则tree[ 8]=arr[ 1]+arr[ 2]+...+arr[ 8 ] 四、前缀和查询（getSum） 求前i项和sum(i)的步骤： 初始化sum=0 从i开始，每次将tree[ i ]加入sum 将i减去lowbit(i)：i = i - lowbit(i) 重复步骤2-3直到i=0 示例：求前7项和（i=7） 7的二进制111，lowbit=1：加tree[ 7]（仅arr[ 7 ]） 7-1=6，lowbit=2：加tree[ 6]（arr[ 5..6 ]） 6-2=4，lowbit=4：加tree[ 4]（arr[ 1..4 ]） 4-4=0：结束。sum=tree[ 7]+tree[ 6]+tree[ 4 ] 五、单点更新（update） 更新arr[ i ]增加delta时： 从i开始，每次将tree[ i ]增加delta 将i加上lowbit(i)：i = i + lowbit(i) 重复直到i超出数组范围 示例：更新arr[ 5 ]（i=5） 5的二进制101，lowbit=1：更新tree[ 5 ] 5+1=6，lowbit=2：更新tree[ 6 ] 6+2=8，lowbit=8：更新tree[ 8 ] 继续直到边界 六、初始化构建 初始化tree全0 对每个arr[ i]执行update(i, arr[ i ])，时间复杂度O(n log n) 优化方法：可直接用O(n)建树，通过子节点累加至父节点 七、与线段树对比 优点：代码简洁、常数小、节省空间 缺点：仅支持前缀和操作（但可通过变形支持区间更新） 线段树功能更通用但实现复杂 通过这种基于二进制索引的设计，Fenwick树以极小的开销实现了动态前缀和的高效维护，是处理频繁更新和查询场景的经典解决方案。