Fenwick Tree (树状数组) 模板详解

Fenwick Tree (树状数组) 模板详解

1. 简介

树状数组（Fenwick Tree 或 Binary Indexed Tree，简称 BIT）是一种支持单点修改和区间查询的数据结构。它的主要特点是：

  1. 实现简单，代码量小
  2. 时间复杂度为 O(log n)
  3. 空间复杂度为 O(n)
  4. 支持动态维护前缀和

2. 实现原理

2.1 基本概念

树状数组巧妙地利用了整数的二进制表示，通过 lowbit 运算（x & -x）来维护数组的前缀和信息。每个节点存储的是原始数组中一段区间的和。

2.2 核心操作

  1. 单点修改：更新一个位置的值，同时维护其影响的所有区间
  2. 前缀和查询：查询从开始到指定位置的元素和
  3. 区间查询：通过两次前缀和查询的差值得到
  4. 二分查找：查找第一个使前缀和大于给定值的位置

3. 模板代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i != 0; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur += a[x - 1];
            }
        }
        return x;
    }
};

4. 函数说明

4.1 构造函数和初始化

1
2
Fenwick(int n_ = 0)
void init(int n_)
  • 支持默认构造和指定大小构造
  • init 函数初始化大小为 n 的树状数组
  • 所有元素初始化为类型 T 的默认值

4.2 单点修改

1
void add(int x, const T &v)
  • 将位置 x 的值增加 v
  • 时间复杂度：O(log n)
  • x 的范围是 [0, n-1]

4.3 前缀和查询

1
T sum(int x)
  • 计算区间 [0, x) 的元素和
  • 时间复杂度：O(log n)
  • x 的范围是 [0, n]

4.4 区间查询

1
T rangeSum(int l, int r)
  • 计算区间 [l, r) 的元素和
  • 通过两次前缀和查询实现
  • 时间复杂度：O(log n)

4.5 二分查找

1
int select(const T &k)
  • 查找第一个使前缀和大于 k 的位置
  • 时间复杂度：O(log n)
  • 返回值范围是 [0, n]

5. 时间复杂度分析

  • 初始化：O(n)
  • 单点修改：O(log n)
  • 前缀和查询：O(log n)
  • 区间查询：O(log n)
  • 二分查找：O(log n)

6. 应用场景

  1. 动态维护前缀和
  2. 区间查询问题
  3. 统计逆序对
  4. 动态维护排名
  5. 区间更新（差分）

7. 注意事项

  1. 下标从 0 开始，内部实现时需要注意 +1 和 -1 的转换
  2. 模板支持任意类型 T，但要求 T 支持加法运算和默认构造
  3. 区间查询返回的是左闭右开区间 [l, r) 的结果
  4. 二分查找函数在所有前缀和都不大于 k 时返回 n

8. 优化技巧

  1. 使用位运算 i & -i 计算 lowbit
  2. 区间查询使用两次前缀和的差值
  3. 二分查找时使用位运算优化
  4. 可以扩展支持区间修改（差分）

9. 总结

树状数组是一种非常实用的数据结构，它在处理动态区间查询问题时表现优秀。相比线段树，它的代码更简洁，常数更小，但功能相对较少。在实际应用中，如果只需要支持单点修改和区间查询，树状数组是一个很好的选择。