树状数组

树状数组（Fenwick Tree，也称为Binary Indexed Tree，BIT）是一种用于高效处理区间求和（或其他类似操作）的数据结构。它具有较低的内存消耗，能够在 O(log n) 的时间内更新单个元素和计算前缀和。

树状数组适用于处理动态数组中的元素累加操作，如频繁更新某个位置的值以及查询某个区间的和等情况。

以下是一个简单的 Java 实现示例，用于构建和使用树状数组：

public class FenwickTree {
    private int[] fenwickTree;

    public FenwickTree(int size) {
        fenwickTree = new int[size + 1]; // 数组下标从1开始
    }

    public void update(int index, int value) {
        while (index < fenwickTree.length) {
            fenwickTree[index] += value;
            index += index & -index; // 增加下一个相关的位置
        }
    }

    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += fenwickTree[index];
            index -= index & -index; // 减去最后一个被包含的元素
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] input = {1, 3, 5, 7, 9, 11};

        FenwickTree fenwickTree = new FenwickTree(input.length);

        // 构建树状数组
        for (int i = 0; i < input.length; i++) {
            fenwickTree.update(i + 1, input[i]);
        }

        // 查询前缀和
        System.out.println(fenwickTree.query(3)); // 输出 9 (1 + 3 + 5)
        System.out.println(fenwickTree.query(6)); // 输出 36 (1 + 3 + 5 + 7 + 9 + 11)
    }
}

在上述代码中，FenwickTree 类用于实现树状数组。update 方法用于更新树状数组中的一个元素，query 方法用于查询前缀和。树状数组中的数组大小比原始数组大小多1，因为树状数组的下标从1开始。

这只是一个简单的树状数组实现示例。在实际应用中，您可能需要考虑更多的功能和优化，以满足不同的需求。