树状数组

基础与数据结构

说明

用二进制低位维护前缀和；单点更新与前缀查询均为 O(log n)。

分析

索引 i 的最低有效位决定当前节点负责的区间长度。Add 沿相关节点向上更新，Prefix 沿区间分解向前累加，因此两者都只经过对数个节点。

外部Prefix(2)转换成内部3，读取tree[3]覆盖外部位置2，再读取tree[2]覆盖位置0到1。查询包含下标2，结果为8；更新加lowbit，查询减lowbit，两种方向不可混淆。

查看图表代码

适用前提与边界

它很适合单点更新和前缀和；复杂区间操作通常需要线段树。 更新下标需满足0≤i<n；特别是Add(-1,delta)会卡在内部下标0，调用前必须校验。Prefix使用包含终点的语义，不能误用半开区间。

示例输入与调用

tree := NewFenwick(4)
	tree.Add(0, 3)
	tree.Add(2, 5)
	fmt.Println(tree.Prefix(2))

运行输出

8

完整 Go 示例

package main

import "fmt"

type Fenwick []int

func NewFenwick(n int) Fenwick {
	return make(Fenwick, n+1)
}
func (f Fenwick) Add(i, delta int) {
	for i++; i < len(f); i += i & -i {
		f[i] += delta
	}
}
func (f Fenwick) Prefix(i int) int {
	s := 0
	for i++; i > 0; i -= i & -i {
		s += f[i]
	}
	return s
}

func main() {
	tree := NewFenwick(4)
	tree.Add(0, 3)
	tree.Add(2, 5)
	fmt.Println(tree.Prefix(2))
}