c++树状数组模板Fenwick (Binary Indexed) Trees

什么是树状数组？

树状数组，也称为二叉索引树(Fenwick (Binary Indexed) Trees
)，用于高效地计算动态序列的前缀和。
1994年，树状数组的发明者 Peter M. Fenwick 在 SOFTWARE PRACTICE AND EXPERIENCE 上以 A New Data Structure for Cumulative Frequency Tables 为题发表文章，首次描述树状数组。

例如，给定一个数组 arr[] ，要对它执行以下两种类型的操作：
1.修改存储在索引 i 处的值。（单点更新）
2.查找前 k 个元素的前缀和。（前缀和查询）

这个问题很容易用暴力算法实现：

int arr[MAXN];
void update(int i, int v) {  // arr[i] 改为 v  
    arr[i] = v;   
}
int prefix_sum(int k)  {  // 返回前 k 个元素的前缀和  
    int sum = 0;
    for(int i = 0; i < k; i++)
        sum += arr[i];
    return sum;
}

但不幸的是，计算前缀和所需的时间是 O(n)，如果执行大量混合操作时，这通常会超时。

一种高效的解决方案是使用线段树，它可以在 O(logn) 时间内执行这两种操作。

使用树状数组，我们也可以在 O(logn) 时间内执行这两个任务。但是，既然线段树可以完成此类工作，为什么还要学习另一种数据结构呢？

这是因为树状数组需要更少的空间，并且在编程竞赛中非常容易实现（整个代码不超过 8-10 行）。

树状数组（Fenwick Tree）的基本概念

一、定义与核心思想

树状数组是一种高效的数据结构，用于处理区间查询和单点更新问题（如求前缀和、区间和、逆序数等）。其核心思想是通过树状结构将数据分组，利用二进制位运算（如lowbit操作）实现快速的前缀和计算与更新操作，时间复杂度均为 (O(\log n))，空间复杂度为 (O(n))，适用于大量更新和查询的场景。

二、核心特性与术语

1. lowbit操作

   • 定义：lowbit(x) 表示 x 的二进制表示中最低位的1所对应的值。
   • 公式：lowbit(x) = x & (-x))（利用补码性质提取最低位1）。
   • 示例：
     • (x = 6)（二进制 110），lowbit(6) = 2（二进制 10）。
     • (x = 8)（二进制 1000），lowbit(8) = 8。

2. 数组结构

   • 树状数组用数组 (arr) 表示，其中每个节点 (C[i]) 负责维护某个区间的信息。
   • 节点 (arr[i]) 对应的区间长度为 lowbit(i)，区间右端点为 i，左端点为 i - lowbit(i) + 1。
   • 示例：
     • (i = 6)（lowbit(6)=2），对应区间为 [5, 6]（长度为2）。
     • (i = 8)（lowbit(8)=8），对应区间为 [1, 8]（长度为8）。

3. 父节点与子节点关系

   • 节点 i 的父节点为 i + lowbit(i)。
   • 节点 i 的子节点为 i - lowbit(i)。

三、基本操作

树状数组支持以下两种核心操作：

1. 单点更新（Update）

   • 功能：将数组中某一位置 x 的值增加 delta。
   • 步骤：
     1. 从位置 x开始，向上更新所有包含 x 的父节点。
     2. 每次更新位置 i后，令 i = i + lowbit(i)，直至超过数组长度。
   • 示例（更新 x=3，delta=5）：
     3→4→8(路径为 x+lowbit(x) 的递增序列)

2. 前缀和查询（Query）

   • 功能：计算数组前 x 项的和 S(x) = a₁ + a₂ + … + a_x。
   • 步骤：
     1. 从位置 x 开始，累加所有包含在区间 ([1, x]) 内的节点值。
     2. 每次累加位置 i 后，令 i = i - lowbit(i)，直至 i=0。
   • 示例（查询前5项和）：
     5→4→0(累加 C[5]+C[4])

四、与线段树的对比

五、典型应用场景

1. 前缀和与区间和计算

   • 计算前 x 项和：直接调用前缀和查询。
   • 计算区间 [l, r]的和：S( r ) - S( l-1 )。

2. 逆序数统计

   • 通过离散化将元素值映射到数组下标，利用树状数组动态维护前缀和，统计逆序对数量。

3. 动态维护集合元素排名

   • 插入元素时查询比当前元素小的元素个数，实现排名统计。

六、代码示例（c++）

树状数组核心：

// 原数组索引 x 的元素加数值 "val"，可正可负
void add(int x, int val) {
  for(; x <= n; x += x&-x)
    BIT[x] += val;
}
// 返回原数组前 x 个元素的和
int query(int x) {
  int sum = 0;
  for(; x > 0; x -= x&-x)
    sum += BIT[x];
  return sum;
}

离散化:

int main() {
  cin >> n;
  vector<int> tmp(n+1);
  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
    tmp[i] = arr[i];
  }
  sort(tmp.begin()+1,tmp.end());
  int m = unique(tmp.begin()+1,tmp.end()) - (tmp.begin()+1);
  for (int i = 1; i <= n; i++) {
    rnk[i] = lower_bound(tmp.begin()+1,tmp.begin()+m+1,arr[i]) - tmp.begin();
  }
  
  long long ans = 0;
  for (int i = n; i >= 1; i--) {
    ans += query(rnk[i]-1);
    add(rnk[i],1);
  }
  cout << ans << endl;
  return 0;
}

七、总结

树状数组以其高效的时间复杂度和简洁的实现，成为处理单点更新+前缀和查询问题的首选数据结构。理解其核心的二进制分组思想和lowbit操作是掌握树状数组的关键，进一步结合差分思想还能扩展到区间更新场景。实际应用中，需根据问题特性（如是否涉及区间操作）选择树状数组或线段树。