树状数组详解（Java实现与前缀和优化技巧）

核心思想：lowbit 函数

树状数组的关键在于 lowbit(x) 函数，它返回 x 的二进制表示中最低位的 1 所对应的值。例如：

• lowbit(6) = lowbit(110₂) = 10₂ = 2
• lowbit(8) = lowbit(1000₂) = 1000₂ = 8

在 Java 中，lowbit 可以通过位运算高效实现：

public static int lowbit(int x) {    // 利用补码特性：x & (-x)    return x & (-x);}

树状数组的结构

假设原数组为 a[1...n]（注意：树状数组通常从下标 1 开始），我们构建一个树状数组 tree[1...n]，其中：

tree[i] = a[i - lowbit(i) + 1] + ... + a[i]

也就是说，tree[i] 负责维护从 i - lowbit(i) + 1 到 i 这一段区间的和。

Java 实现树状数组

下面我们用 Java 完整实现一个支持单点更新和前缀和查询的树状数组：

public class FenwickTree {    private int[] tree;    private int n;    // 构造函数    public FenwickTree(int size) {        this.n = size;        this.tree = new int[n + 1]; // 下标从1开始，所以多申请一位    }    // lowbit 函数    private int lowbit(int x) {        return x & (-x);    }    // 单点更新：在 index 位置加上 delta    public void update(int index, int delta) {        // 注意：外部调用时 index 从 0 开始，内部转为 1-based        index++;        while (index <= n) {            tree[index] += delta;            index += lowbit(index);        }    }    // 查询前缀和 [0, index]    public int query(int index) {        index++;        int sum = 0;        while (index > 0) {            sum += tree[index];            index -= lowbit(index);        }        return sum;    }    // 查询区间和 [left, right]    public int rangeQuery(int left, int right) {        if (left == 0) {            return query(right);        }        return query(right) - query(left - 1);    }}

使用示例

下面是一个完整的使用例子，展示如何初始化、更新和查询：

public class Main {    public static void main(String[] args) {        int[] arr = {1, 3, 5, 7, 9, 11};        FenwickTree ft = new FenwickTree(arr.length);        // 初始化树状数组        for (int i = 0; i < arr.length; i++) {            ft.update(i, arr[i]);        }        System.out.println("前缀和 [0, 3]: " + ft.query(3)); // 输出 1+3+5+7 = 16        System.out.println("区间和 [2, 4]: " + ft.rangeQuery(2, 4)); // 输出 5+7+9 = 21        // 更新 index=2 的值加 2        ft.update(2, 2);        System.out.println("更新后前缀和 [0, 3]: " + ft.query(3)); // 输出 18    }}

为什么树状数组这么高效？

树状数组之所以高效，是因为它利用了二进制的特性，每次操作只涉及 O(log n) 个节点。无论是更新还是查询，都沿着树的路径向上或向下跳转，而跳转的步长由 lowbit 决定。

应用场景

Java树状数组常用于以下场景：

• 动态前缀和问题
• 逆序对计数
• 区间更新 + 单点查询（配合差分数组）
• 在线统计问题

总结

树状数组（二叉索引树）是一种简洁而强大的数据结构，特别适合处理动态前缀和问题。通过掌握 lowbit 函数和两个核心操作（update 和 query），你就能在 O(log n) 时间内完成更新和查询。对于追求效率的 Java 开发者来说，这是必须掌握的前缀和优化技巧之一。

希望这篇教程能帮助你彻底理解树状数组！动手写一遍代码，你会掌握得更牢固。