原文件标题同时包含“树状数组”和“线段树”，但正文只讨论了树状数组。本文将标题调整为更准确的“树状数组”；线段树适合更复杂的区间操作，可以单独整理为另一篇文章。

树状数组（Fenwick Tree）适合维护满足结合性的前缀信息，最常见的组合是：

  • 单点增加，查询前缀和。
  • 单点增加，查询区间和。
  • 结合离散化统计频次、逆序对等问题。

一、lowbit

树状数组内部使用 1 开始的下标。定义：

int lowbit(int index) {
  return index & -index;
}

lowbit(index) 表示二进制表示中最低位的 1 对应的数值。例如：

index = 12 = 1100（二进制）
lowbit(index) = 4 = 0100（二进制）

树状数组的第 i 个位置维护一段长度为 lowbit(i) 的连续区间。更新时不断加上 lowbit(i)，查询时不断减去 lowbit(i)，因此两个操作的复杂度都是 O(log n)。

二、基本实现

对外接口使用从 0 开始的下标，内部再转换成从 1 开始的下标：

#include <vector>

class FenwickTree {
public:
  explicit FenwickTree(int size) : tree_(size + 1, 0) {}

  // nums[index] 增加 delta。
  void Add(int index, long long delta) {
    for (++index; index < static_cast<int>(tree_.size());
         index += index & -index) {
      tree_[index] += delta;
    }
  }

  // 返回 nums[0:end) 的和。
  long long PrefixSum(int end) const {
    long long result = 0;
    for (int index = end; index > 0; index -= index & -index) {
      result += tree_[index];
    }
    return result;
  }

  // 返回 nums[left:right) 的和。
  long long RangeSum(int left, int right) const {
    return PrefixSum(right) - PrefixSum(left);
  }

private:
  std::vector<long long> tree_;
};

例如，数组 nums 的区间 [left, right) 和可以表示为：

FenwickTree tree(static_cast<int>(nums.size()));
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
  tree.Add(i, nums[i]);
}

long long result = tree.RangeSum(left, right);

如果一开始就有完整数组，也可以使用线性时间的 Fenwick Tree 建树；逐个调用 Add 的写法更直观，建树复杂度为 O(n log n)。

三、使用树状数组统计逆序对

如果 i < j 且 nums[i] > nums[j]，则 (i, j) 是一个逆序对。

从右向左遍历数组。处理 nums[i] 时，树状数组中保存的是右侧已经出现的元素，因此查询比 nums[i] 小的元素数量，就得到了以 i 为左端点的逆序对数量。

如果数值范围很大，需要先进行离散化：将所有值排序去重，再把原值映射为排名。

#include <algorithm>
#include <vector>

long long CountInversions(const std::vector<int>& nums) {
  std::vector<int> values = nums;
  std::sort(values.begin(), values.end());
  values.erase(std::unique(values.begin(), values.end()), values.end());

  FenwickTree tree(static_cast<int>(values.size()));
  long long result = 0;

  for (int i = static_cast<int>(nums.size()) - 1; i >= 0; --i) {
    const int rank = static_cast<int>(
        std::lower_bound(values.begin(), values.end(), nums[i]) -
        values.begin());

    // PrefixSum(rank) 统计排名小于 rank 的元素。
    result += tree.PrefixSum(rank);
    tree.Add(rank, 1);
  }

  return result;
}

总时间复杂度为 O(n log n)，空间复杂度为 O(n)。

四、树状数组和线段树的选择

数据结构 典型操作 单次复杂度
树状数组 单点修改、区间和 O(log n)
线段树 区间修改、区间查询、区间最值 O(log n)

如果问题只需要单点修改和前缀性质的查询，树状数组代码更短、常数更小。如果需要区间修改、区间最值或更复杂的合并逻辑，可以考虑线段树。

五、总结

  • 树状数组使用 lowbit 将前缀划分为若干段。
  • 单点修改和前缀查询的时间复杂度都是 O(log n)。
  • 通过前缀和之差可以查询任意区间和。
  • 离散化后，树状数组可以用于统计逆序对和频次。
  • 树状数组适合简单的前缀聚合，复杂区间操作更适合线段树。