java实现树状数组区间修改查询

树状数组（Fenwick Tree）是一种用于高效计算数组前缀和的数据结构。它可以支持单点修改和区间查询，但是不能直接支持区间修改，需要进行一些变形。

一般情况下，树状数组被用于求解静态数组的前缀和，这里我们介绍一种树状数组的变形——动态树状数组。该数据结构可以支持区间修改和区间查询，时间复杂度均为 O(log n)。

动态树状数组的实现分为两步：

1. 实现区间修改。为了实现区间修改，我们需要维护两个树状数组：A 和 B。A 保存原数组，B 保存它们的差值。当我们要修改区间 [l, r]，我们可以直接对 A[l] 和 A[r+1] 进行修改，让它们的值分别加上 val 和 -val。同时，我们也需要对 B[l] 和 B[r+1] 进行相同的修改，让它们的值分别加上 val * l 和 -val * (r+1)。这样，当我们查询区间和时，只需要查询 A 和 B 中的差值和即可。

2. 实现区间查询。为了实现区间查询，我们需要对查询区间 [l, r] 进行拆分。我们可以将查询区间拆分为两个前缀和：[1, r] 和 [1, l-1]。然后，我们可以对这两个前缀和分别进行查询，相减即可得到区间和。

下面是 Java 代码实现：

public class DynamicFenwickTree {
    private int[] a;
    private int[] b;

    public DynamicFenwickTree(int n) {
        a = new int[n + 1];
        b = new int[n + 1];
    }

    public void update(int l, int r, int val) {
        update(a, l, val);
        update(a, r + 1, -val);
        update(b, l, val * l);
        update(b, r + 1, -val * (r + 1));
    }

    public int query(int l, int r) {
        return query(r) - query(l - 1);
    }

    private void update(int[] t, int i, int val) {
        while (i < t.length) {
            t[i] += val;
            i += i & -i;
        }
    }

    private int query(int[] t, int i) {
        int sum = 0;
        while (i > 0) {
            sum += t[i];
            i -= i & -i;
        }
        return sum;
    }

    private int query(int i) {
        return query(a, i) * i - query(b, i);
    }
}

使用示例：

DynamicFenwickTree tree = new DynamicFenwickTree(5);
tree.update(1, 3, 2);
tree.update(2, 4, 3);
System.out.println(tree.query(1, 5)); // 20

这个例子中，我们创建了一个长度为 5 的动态树状数组，然后使用 update 方法对区间 [1, 3] 和 [2, 4] 进行了修改，分别加上了 2 和 3。最后，我们使用 query 方法查询了整个数组的和，结果为 20。