树状数组

概念讲解

什么是树状数组？

树状数组（Binary Indexed Tree，BIT）是一种支持单点修改和区间查询的数据结构。

lowbit 操作

123int lowbit(int x) {
    return x & (-x);
}

基本操作

单点修改

12345678const int N = 100005;
int tree[N];

void update(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += c;
    }
}

区间查询（前缀和）

123456789101112int query(int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}

// 区间 [l, r] 的和
int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}

时间复杂度

操作 时间复杂度
单点修改 O(log n)
区间查询 O(log n)

应用

  1. 单点修改 + 区间查询
  2. 求逆序对
  3. 离散化

考点分析

初赛考查方式

  1. 程序阅读： 树状数组操作
  2. 编程题： 区间查询

常见考点

  • lowbit 操作
  • 单点修改
  • 区间查询

例题精讲

例题 1：区间求和

题目： 单点修改，区间求和。

解答：

12update(x, c);  // a[x] += c
int sum = query(r) - query(l - 1);  // [l, r] 的和

练习题

  1. lowbit 的作用是什么？
查看答案

lowbit 的作用是找到最低位的 1，用于确定树状数组的管辖范围。

123int lowbit(int x) {
    return x & (-x);
}

例如：lowbit(6) = 2，因为 6 = 110₂，最低位的 1 是 10₂ = 2。

  1. 树状数组的时间复杂度是多少？
查看答案

树状数组的时间复杂度：

  • 单点修改：O(log⁡n)O(\log n)
  • 区间查询：O(log⁡n)O(\log n)
  1. 如何用树状数组求逆序对？
查看答案

用树状数组求逆序对：

  1. 离散化：将值域映射到 1~n
  2. 从右往左遍历：对于每个元素，查询比它小的元素个数
  3. 累加答案：逆序对数 = 查询结果之和
12345int count = 0;
for (int i = n; i >= 1; i--) {
    count += query(a[i] - 1);
    update(a[i], 1);
}

易错点

⚠️ 注意：

  1. 下标从 1 开始
  2. lowbit 是关键
  3. 注意边界条件
  4. 区间修改需要差分