树状数组（Fenwick Tree / Binary Indexed Tree）
一句话说明
树状数组专门干两件事：单点修改和前缀和查询，而且都能压到
O(log n)。
Go 代码
type FenwickTree struct {
n int
tree []int
}
func NewFenwickTree(n int) *FenwickTree {
return &FenwickTree{n: n, tree: make([]int, n+1)}
}
func (ft *FenwickTree) lowbit(x int) int {
return x & -x
}
func (ft *FenwickTree) Update(index, delta int) {
for index <= ft.n {
ft.tree[index] += delta
index += ft.lowbit(index)
}
}
func (ft *FenwickTree) Query(index int) int {
sum := 0
for index > 0 {
sum += ft.tree[index]
index -= ft.lowbit(index)
}
return sum
}
func (ft *FenwickTree) RangeQuery(left, right int) int {
return ft.Query(right) - ft.Query(left-1)
}关键点
lowbit 决定当前节点覆盖的区间长度，所以更新和查询都能沿着二进制位跳转。