树状数组模板

一句话说明

树状数组模板的关键就两句：查询时 i -= lowbit(i)，更新时 i += lowbit(i)。

模板适用场景

• 单点增加
• 前缀和查询
• 区间和查询
• 离散化后的计数统计

如果题目变成区间最值、复杂区间更新，直接转向 线段树模板。

Go 模板：标准 Fenwick

type Fenwick struct {
    size int
    tree []int
}
 
func NewFenwick(size int) *Fenwick {
    return &Fenwick{
        size: size,
        tree: make([]int, size+1),
    }
}
 
func BuildFenwick(nums []int) *Fenwick {
    f := NewFenwick(len(nums))
    for i, v := range nums {
        f.Add(i+1, v)
    }
    return f
}
 
func lowbit(x int) int {
    return x & -x
}
 
func (f *Fenwick) Add(index, delta int) {
    for index <= f.size {
        f.tree[index] += delta
        index += lowbit(index)
    }
}
 
func (f *Fenwick) PrefixSum(index int) int {
    sum := 0
    for index > 0 {
        sum += f.tree[index]
        index -= lowbit(index)
    }
    return sum
}
 
func (f *Fenwick) RangeSum(left, right int) int {
    if left > right {
        return 0
    }
    return f.PrefixSum(right) - f.PrefixSum(left-1)
}

这个模板的状态定义

tree[i] 表示一段长度为 lowbit(i) 的区间和

也就是说，tree[i] 不是简单地存某个单点，而是在存一个二进制分组后的区间贡献。

下标约定一定先统一

这个模板默认：

• 内部使用 1 下标
• 原数组第 0 位对应树状数组第 1 位

所以题目如果给的是 0 下标，通常要：

index + 1

再去更新或查询。

常用变形：区间和

区间 [left, right] 的和本质上还是两个前缀相减：

sum(left..right) = prefix(right) - prefix(left-1)

这是树状数组最常见的题型。

易错点

树状数组模板最容易错的地方

• 更新时下标不能从 0 开始，否则会死循环。
• RangeSum 本质是两个前缀和相减。
• 题目如果是赋值更新，要先算差值再 Add。
• 模板最适合单点改，不要强行拿它做复杂区间维护。

复杂度

操作	时间复杂度	空间复杂度
单点更新	O(log n)	O(n)
前缀和	O(log n)	O(1)
区间和	O(log n)	O(1)

相关主题

• 树状数组
• 线段树模板
• 前缀和与差分

---

返回：算法模板