树状数组（Fenwick Tree / Binary Indexed Tree）
一句话说明
树状数组本质上是在用二进制分组维护前缀和，所以它特别擅长“单点修改 + 前缀查询 / 区间求和”。
先抓住核心直觉
普通前缀和数组查询很快，但一旦修改某个元素，后面整段前缀都要重算。
树状数组的思路是：
- 不直接存原数组前缀
- 而是让
tree[i]维护一小段区间和 - 这段区间长度由
lowbit(i)决定
例如：
tree[1] 管 1 个元素
tree[2] 管 2 个元素
tree[4] 管 4 个元素
tree[8] 管 8 个元素所以查询前缀和时，我们不断跳到“前一个负责块”；更新时，我们不断跳到“下一个受影响块”。
lowbit 到底是什么意思
lowbit(x) = x & -x它表示 x 二进制中最低位的 1 所对应的值。
6 = 110b, lowbit(6) = 10b = 2
8 = 1000b, lowbit(8) = 1000b = 8这就是树状数组跳转的关键：
- 查询前缀和：
i -= lowbit(i) - 更新节点值：
i += lowbit(i)
你可以把它记成两个不变量
tree[i]维护的是区间[i-lowbit(i)+1, i]的和- 所有前缀和都可以拆成若干个这样的区间
这两个点一旦记住，树状数组就不容易写错。
Go 代码：基础模板
type Fenwick struct {
n int
tree []int
}
func NewFenwick(n int) *Fenwick {
return &Fenwick{
n: n,
tree: make([]int, n+1),
}
}
func lowbit(x int) int {
return x & -x
}
// add: 下标 idx 加上 delta。这里 idx 从 1 开始。
func (f *Fenwick) Add(idx, delta int) {
for idx <= f.n {
f.tree[idx] += delta
idx += lowbit(idx)
}
}
// PrefixSum: 查询区间 [1..idx] 的和。
func (f *Fenwick) PrefixSum(idx int) int {
sum := 0
for idx > 0 {
sum += f.tree[idx]
idx -= lowbit(idx)
}
return sum
}
// RangeSum: 查询区间 [left..right] 的和。
func (f *Fenwick) RangeSum(left, right int) int {
if left > right {
return 0
}
return f.PrefixSum(right) - f.PrefixSum(left-1)
}从数组建树
如果题目给的是原数组，最直接的写法就是逐个 Add。
func BuildFenwick(nums []int) *Fenwick {
f := NewFenwick(len(nums))
for i, v := range nums {
f.Add(i+1, v)
}
return f
}如果不是特别卡常，这个写法已经够用，而且最不容易错。
常见题型 1：单点修改 + 区间求和
这是最标准的形态，比如 LeetCode 307。
type NumArray struct {
nums []int
bit *Fenwick
}
func Constructor(nums []int) NumArray {
bit := BuildFenwick(nums)
copyNums := append([]int(nil), nums...)
return NumArray{
nums: copyNums,
bit: bit,
}
}
func (na *NumArray) Update(index int, val int) {
delta := val - na.nums[index]
na.nums[index] = val
na.bit.Add(index+1, delta)
}
func (na *NumArray) SumRange(left int, right int) int {
return na.bit.RangeSum(left+1, right+1)
}常见题型 2：区间加 + 单点查
这个套路本质上是：
- 先对原数组做差分
- 再对差分数组上树状数组
这样区间修改会变成两个端点更新。
type RangeAddPointQuery struct {
n int
tree []int
}
func NewRangeAddPointQuery(n int) *RangeAddPointQuery {
return &RangeAddPointQuery{
n: n,
tree: make([]int, n+1),
}
}
func (r *RangeAddPointQuery) add(idx, delta int) {
for idx <= r.n {
r.tree[idx] += delta
idx += lowbit(idx)
}
}
func (r *RangeAddPointQuery) AddRange(left, right, delta int) {
r.add(left, delta)
if right+1 <= r.n {
r.add(right+1, -delta)
}
}
func (r *RangeAddPointQuery) Query(idx int) int {
sum := 0
for idx > 0 {
sum += r.tree[idx]
idx -= lowbit(idx)
}
return sum
}为什么它常和离散化一起出现
树状数组下标必须是连续整数。
但很多题目里的数值范围很大，比如：
- 值域到
10^9 - 有负数
- 只出现几万个不同值
这时就先离散化，把真实数值映射到 1..m，然后再把树状数组挂上去。
func Discretize(nums []int) map[int]int {
arr := append([]int(nil), nums...)
sort.Ints(arr)
rank := make(map[int]int)
idx := 1
for _, v := range arr {
if _, ok := rank[v]; ok {
continue
}
rank[v] = idx
idx++
}
return rank
}复杂度
| 操作 | 时间复杂度 |
|---|---|
| 单点修改 | O(log n) |
| 前缀和查询 | O(log n) |
| 区间和查询 | O(log n) |
| 空间 | O(n) |
什么时候优先想到树状数组
- 题目是前缀和 / 区间和
- 需要动态修改
- 只做单点更新
- 还会配合离散化统计“前面有多少个数比它小 / 大”
如果题目变成下面这种，就该优先考虑 线段树：
- 区间最值
- 区间赋值
- 多种复杂区间信息合并
易错点
写树状数组最容易错的地方
- 内部实现通常使用
1下标，不要和题目的0下标混掉。RangeSum(left, right)一般要写成两个前缀和相减。- 离散化后，记得把值映射成连续下标再更新。
- 树状数组不是万能区间结构，它最擅长的是“可逆前缀信息”，不是任意区间维护。
经典题目
- 区域和检索 - 数组可修改 - LeetCode 307
- 计算右侧小于当前元素的个数 - LeetCode 315
- 翻转对 - LeetCode 493
- 区间和的个数 - LeetCode 327