树状数组

【树状数组】(Binary Indexed Tree，简称BIT，又称Fenwick Tree)是一种用于高效处理数组前缀和的数据结构。它支持单点修改和区间查询操作，这两种操作的时间复杂度都是 O(log n)。

基本原理

树状数组的核心思想是利用数的二进制表示，将前缀和分解为多个部分。树状数组中的每个节点存储原始数组中一段区间的和。

关键操作

树状数组基于以下两个关键操作：

• lowbit(x)：返回x二进制表示中最低位的1所对应的值
• 例如：lowbit(12) = lowbit(1100₂) = 4 = 100₂

数据结构表示

树状数组本质上是一个数组，通常用数组 tree[] 表示：

• tree[i] 存储的是序列中一段元素的和
• 具体来说，tree[i] 存储的是从 i - lowbit(i) + 1 到 i 这一段区间内的元素和

核心操作实现

1. lowbit函数

// 计算x的二进制表示中最低位1所对应的值
int lowbit(int x) {
    return x & (-x);
}

2. 更新操作(单点修改)

// 在位置idx上增加值val
void update(int idx, int val) {
    while (idx <= n) {     // n是数组长度
        tree[idx] += val;
        idx += lowbit(idx); // 更新受影响的所有节点
    }
}

3. 查询操作(求前缀和)

// 计算前缀和：从1到idx的元素和
int query(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += tree[idx];
        idx -= lowbit(idx); // 向前查找
    }
    return sum;
}

4. 区间查询

要查询区间[l, r]的和，可以利用前缀和的性质：

int queryRange(int l, int r) {
    return query(r) - query(l - 1);
}

完整代码示例

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;
int tree[MAXN];
int n;  // 数组长度

// 计算lowbit
inline int lowbit(int x) {
    return x & (-x);
}

// 单点更新
void update(int idx, int val) {
    while (idx <= n) {
        tree[idx] += val;
        idx += lowbit(idx);
    }
}

// 查询前缀和
int query(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += tree[idx];
        idx -= lowbit(idx);
    }
    return sum;
}

// 初始化树状数组
void buildBIT(vector<int>& nums) {
    n = nums.size();
    for (int i = 0; i < n; i++) {
        update(i + 1, nums[i]);  // 注意：树状数组从1开始索引
    }
}

// 区间查询
int queryRange(int l, int r) {
    return query(r) - query(l - 1);
}

int main() {
    vector<int> nums = {1, 3, 5, 7, 9, 11};
    buildBIT(nums);

    cout << "前缀和(1到3): " << query(3) << endl;       // 输出：1+3+5=9
    cout << "区间和(3到5): " << queryRange(3, 5) << endl; // 输出：5+7+9=21

    // 将位置2的值增加4
    update(2, 4);
    cout << "更新后的前缀和(1到3): " << query(3) << endl; // 输出：1+(3+4)+5=13

    return 0;
}

时间复杂度分析

• 单点更新：O(log n)
• 区间查询：O(log n)

树状数组的应用场景

1. 区间求和：快速计算数组的区间和
2. 动态维护前缀和：在频繁更新的情况下维护前缀和
3. 求逆序对数量：通过树状数组优化归并排序
4. 二维/多维前缀和：处理二维或更高维度的前缀和问题

树状数组与线段树的比较

典型应用题目

例题1：逆序对计数

问题描述：给定一个数组，求数组中的逆序对数量(即前面的数比后面的数大的对数)。

解题思路：

1. 从右向左扫描数组
2. 对于每个元素，统计已经扫描过的元素中小于当前元素的数量
3. 利用树状数组维护已扫描元素的计数

int countInversions(vector<int>& nums) {
    // 离散化处理
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

    memset(tree, 0, sizeof(tree));
    n = sorted.size();

    int inversions = 0;
    for (int i = nums.size() - 1; i >= 0; i--) {
        int idx = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin() + 1;
        inversions += query(idx - 1);  // 统计比当前元素小的元素数量
        update(idx, 1);                // 将当前元素加入树状数组
    }

    return inversions;
}

例题2：区间更新与查询

树状数组也可以支持区间更新操作，通过差分数组技巧实现。以下代码演示如何实现区间更新：

// 差分数组的树状数组
int diff[MAXN];  // 差分数组的树状数组

// 区间更新：给区间[l,r]的每个元素加上val
void rangeUpdate(int l, int r, int val) {
    update(diff, l, val);       // 在位置l加上val
    update(diff, r + 1, -val);  // 在位置r+1减去val
}

// 获取位置idx的元素值(前缀和)
int getValue(int idx) {
    return query(diff, idx);
}

注意事项

1. 【索引从1开始】：树状数组通常从索引1开始，处理原始数组时需要偏移
2. 【处理大数组】：树状数组可以处理很大的数组，但需要预先分配足够的空间
3. 【离散化】：当数据范围很大但数据量较小时，可以使用离散化技术

常见错误

1. 树状数组的索引从0开始而不是1
2. 更新函数和查询函数的实现错误
3. 树状数组大小不够

练习题目推荐

1. SPOJ - INVCNT (逆序对计数)
2. POJ 3321 - Apple Tree (树上计数问题)
3. CodeForces 459D - Pashmak and Parmida's Problem