Fenwick tree

Fenwick Tree，又称为树状数组（Binary Indexed Tree），是一种基于数组实现的数据结构，用于高效地动态维护前缀和。它可以在O(logn)的时间内完成以下操作：更新某个元素的值，查询某个区间的和。Fenwick Tree的实现原理是将数组分解为一系列的区间和，每个区间和保存在树状数组的相应位置上。通过使用二进制的技巧，可以高效地计算每个区间和。：

public class FenWickTree {
    private int[] values;
    private int[] bit;

    public FenWickTree(int length) {
        values = new int[length];
        bit = new int[length + 1];
    }

    public void setValues(int index, int value) {
        values[index = value;
        index += 1;
        while (index < bit.length) {
            bit[index += value;
            index += index & -index;
        }
    }

    public int getSum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }
}

以上代码展示了如何使用Fenwick Tree实现动态维护前缀和的功能。其中setValues()方法用于更新某个元素的值，getSum()方法用于查询某个区间的和。

另外，Fenwick Tree也可以用来解决区间修改的问题。对于元素的修改，我们可以视为区间查询的逆过程，通过从叶节点开始向上更新父节点，依次对每个父节点进行相同的修改操作。具体的实现可以参考下面的示例代码：

class FenwickTree {
    private int[] tree;

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

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

    public void add(int i, int val) {
        while (i < tree.length) {
            tree[i += val;
            i += lowbit(i);
        }
    }

    public int query(int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i -= lowbit(i);
        }
        return res;
    }
}

这段代码展示了如何使用Fenwick Tree解决区间修改的问题。add()方法用于修改某个元素，query()方法用于查询某个区间的和。

综上所述，Fenwick Tree是一种用于高效地动态维护前缀和的数据结构，可以在O(logn)的时间内完成更新和查询操作。同时，它也可以应用于区间修改的问题。
#### 引用[.reference_title]
- *1* *3* [【数据结构与算法】树状数组](https://blog.csdn.net/zzy_NIC/article/details/130616434)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* [6.10 Fenwick树](https://blog.csdn.net/m0_66201040/article/details/122923027)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]