树状数组详解与应用

一、树状数组简介

树状数组（Binary Indexed Tree，简称BIT），也称为Fenwick Tree，是一种用于高效处理数组前缀和问题的数据结构。它能够以O(log n)的时间复杂度完成以下操作：

单点更新：修改数组中某一位置的值
区间查询：求解数组中某一区间的和

相比于传统的前缀和数组，树状数组在处理数组元素频繁更新的场景下具有显著优势。

二、树状数组的基本原理

1. 数据存储方式

树状数组本质上是一个数组，但它巧妙地利用了二进制的性质来组织数据。在树状数组中，每个位置i存储的是原数组中一段区间的和，这个区间的长度与i的二进制表示有关。

具体来说，树状数组中的每个元素tree[i]存储的是原数组中从(i-lowbit(i)+1)到i这一段区间的和。其中，lowbit(i)表示i的二进制表示中最低位1所对应的值。

2. lowbit函数解析

树状数组的核心是lowbit函数，它用于获取一个数的二进制表示中最低位1所对应的值。例如：

lowbit(6) = lowbit(110₂) = 2
lowbit(5) = lowbit(101₂) = 1
lowbit(8) = lowbit(1000₂) = 8

在Java中，lowbit函数的实现非常简洁：

1
2
3

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

这个函数利用了补码的性质：对于一个整数x，-x的二进制表示是x的二进制取反加1。因此，x & (-x)的结果恰好是x的二进制表示中最低位1所对应的值。

三、树状数组的基本操作

1. 初始化

树状数组的初始化很简单，只需要创建一个大小为n+1的数组（下标从1开始）：

1	int[] tree = new int[n + 1];

2. 单点更新（update操作）

当我们需要将原数组中位置i的值增加delta时，需要更新树状数组中所有包含位置i的区间。更新的过程如下：

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

这个过程的时间复杂度是O(log n)。

3. 前缀和查询（query操作）

当我们需要查询原数组中从1到i的前缀和时，需要将树状数组中多个区间的和加起来。查询的过程如下：

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

这个过程的时间复杂度也是O(log n)。

4. 区间查询

如果要查询原数组中从l到r的区间和，可以利用前缀和的性质：

1
2
3

int rangeQuery(int[] tree, int l, int r) {
    return query(tree, r) - query(tree, l - 1);
}

四、树状数组的实现示例

以下是一个完整的树状数组实现示例，包括基本的更新和查询操作：

public class FenwickTree {
    private int[] tree;
    private int n;
    
    public FenwickTree(int n) {
        this.n = n;
        tree = new int[n + 1];
    }
    
    // 返回x的二进制表示中最低位1所对应的值
    private int lowbit(int x) {
        return x & (-x);
    }
    
    // 将位置i的值增加delta
    public void update(int i, int delta) {
        for (; i <= n; i += lowbit(i)) {
            tree[i] += delta;
        }
    }
    
    // 查询从1到i的前缀和
    public int query(int i) {
        int sum = 0;
        for (; i > 0; i -= lowbit(i)) {
            sum += tree[i];
        }
        return sum;
    }
    
    // 查询从l到r的区间和
    public int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
}

五、树状数组的应用场景

1. 区间和查询

树状数组最基本的应用是处理区间和查询问题，特别是在数组元素频繁更新的情况下。

2. 逆序对计数

树状数组可以高效地解决逆序对计数问题。通过从右到左遍历数组，对于每个元素，查询比它小的元素的个数，然后将该元素加入树状数组。

3. 二维树状数组

树状数组可以扩展到二维空间，用于处理矩阵的区域和查询问题。

4. 动态维护前缀最值

通过一些技巧，树状数组也可以用于动态维护前缀最大值或最小值。

六、树状数组与线段树的比较

树状数组和线段树都是用于处理区间查询问题的数据结构，但它们各有优缺点：

实现复杂度：树状数组的实现更加简洁，代码量更少。
空间复杂度：树状数组的空间复杂度为O(n)，而线段树的空间复杂度为O(4n)。
功能：线段树功能更加强大，可以处理更复杂的区间操作，如区间修改、区间最值查询等。
常数因子：在实际应用中，树状数组的常数因子通常小于线段树，因此在只需要处理区间和查询的场景下，树状数组可能更快。

七、实际应用示例

以下是一个使用树状数组解决实际问题的示例。这个问题来自于我们的代码库中的一个例子，涉及到对不同颜色点的计数和查询：

static class FenwickTree {
    int n;
    int[] tree;

    public FenwickTree(int n) {
        this.n = n;
        tree = new int[n + 1];
    }

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

    void add(int i, int val) {
        for (; i <= n; i += lowbit(i)) {
            tree[i] += val;
        }
    }

    int preSum(int i) {
        int ret = 0;
        for (; i > 0; i -= lowbit(i)) {
            ret += tree[i];
        }
        return ret;
    }

    int rangeSum(int l, int r) {
        return preSum(r) - preSum(l - 1);
    }
}

// 使用树状数组解决问题
public static void solve() {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    List<int[]> arr = new ArrayList<>();

    // 读入所有的点
    for (int i = 0; i < n; i++) {
        int l = sc.nextInt(); // x坐标
        int w = sc.nextInt(); // y坐标
        int c = sc.nextInt(); // 颜色
        arr.add(new int[]{l, w, c});
    }

    // 对点进行排序，先按x升序，然后按y升序
    arr.sort((o1, o2) -> {
        if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]);
        else return Integer.compare(o1[1], o2[1]);
    });

    // 建立三种颜色对应的树状数组
    FenwickTree[] tree = new FenwickTree[3];
    for (int i = 0; i < 3; i++) tree[i] = new FenwickTree(100010);

    int ans = 0;
    int mod = (int) 1e9 + 7;

    // 枚举排序好的点
    for (int[] a : arr) {
        int l = a[0]; // x坐标
        int w = a[1]; // y坐标
        int c = a[2]; // 颜色
        for (int i = 0; i < 3; i++) {
            if (c == i) continue; // 相同颜色被排除掉
            // 累加答案，计算当前点的有效配对数量
            ans = (ans + tree[i].rangeSum(w + 1, 100010)) % mod;
        }
        // 更新树状数组
        tree[c].add(w, 1);
    }
    System.out.println(ans);
}