如何在 Java 中利用数组实现简单的二进制扇形树（Fenwick Tree）加速区间更新

树状数组（Fenwick Tree）其实可以通过双数组配合差分思想，轻松实现区间更新与区间查询。核心思路是维护两个东西：d[i] 和 (i−1)·d[i]。时间复杂度稳定在 O(log n)，非常适合那些只需要“区间加”和“区间求和”的轻量场景。

其实 Ja va 里并没有“二进制扇形树”这个标准说法——你真正想用的，应该是树状数组（Fenwick Tree）。它基于整数的二进制低位（lowbit）来构造，主要用来高效处理前缀和、单点更新或区间更新查询。不过有一点要注意：经典的 Fenwick Tree 原生只支持单点更新 + 区间查询（或者反过来区间更新 + 单点查询），并不能直接同时支持“区间更新 + 区间查询”。如果想实现像 [l, r] 全部加 delta 并且还能求区间和，那就得引入差分思想，用两个树状数组来协同工作。

核心思路：差分 + 双树状数组

假设原数组是 a[1..n]，先定义它的差分数组 d：

• d[1] = a[1]
• d[i] = a[i] − a[i−1] （i > 1）

这样一来，a[i] 就等于 d[1] + d[2] + … + d[i]，也就是说，a 的前缀和其实就是 d 的前缀和。那么区间更新 a[l..r] += delta 就变成了：

 d[l] += delta，d[r+1] −= delta（如果 r+1 ≤ n）。

但问题来了：此时求 a[l..r] 的和，需要计算一个看起来很复杂的式子：

 ∑ₖ₌ₗʳ a[k] = ∑ₖ₌ₗʳ ∑ⱼ₌₁ᵏ d[j] = ∑ⱼ₌₁ʳ (r−j+1)·d[j] − ∑ⱼ₌₁ˡ⁻¹ (l−j)·d[j]

这事儿听起来有点绕——别担心。整理之后你会发现，它完全可以转化成两个前缀和的形式。于是我们就引入两个 Fenwick Tree：

• tree1 负责维护 d[i]
• tree2 负责维护 (i−1)·d[i]

说到底，只要维护好这两个数组，区间更新和区间查询就能同时搞定。

Ja va 实现：支持区间更新与区间查询的 Fenwick Tree

说到做到，Ja va 实现搞起来。以下是一个完整、可运行的数组实现（1-indexed，下标从 1 开始）：

class FenwickRange {
    private long[] tree1;
    private long[] tree2;
    private int n;

    public FenwickRange(int size) {
        this.n = size;
        this.tree1 = new long[n + 1];
        this.tree2 = new long[n + 1];
    }

    // lowbit 运算：x & (-x)
    private int lowbit(int x) {
        return x & (-x);
    }

    // 向 tree 更新 index 位置 +delta
    private void update(long[] tree, int index, long delta) {
        while (index <= n) {
            tree[index] += delta;
            index += lowbit(index);
        }
    }

    // 查询 tree 前缀和 [1..index]
    private long query(long[] tree, int index) {
        long sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lowbit(index);
        }
        return sum;
    }

    // 区间更新：a[l..r] += delta
    public void rangeUpdate(int l, int r, long delta) {
        // d[l] += delta → tree1[l] += delta, tree2[l] += (l-1)*delta
        update(tree1, l, delta);
        update(tree2, l, (long)(l - 1) * delta);
        // d[r+1] -= delta（若存在）
        if (r + 1 <= n) {
            update(tree1, r + 1, -delta);
            update(tree2, r + 1, (long) r * (-delta));
        }
    }

    // 查询 a[1..x] 的前缀和
    private long prefixSum(int x) {
        return query(tree1, x) * x - query(tree2, x);
    }

    // 查询 a[l..r] 的区间和
    public long rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
}

使用示例也非常直观：

public class Main {
    public static void main(String[] args) {
        FenwickRange ft = new FenwickRange(5);
        // 初始数组 a = [0,1,2,3,4,5]（1-indexed，a[1]=1…a[5]=5）
        // 等价于初始化差分：d[1]=1, d[2]=1, d[3]=1, d[4]=1, d[5]=1
        ft.rangeUpdate(1, 1, 1); // a[1] += 1 → a[1]=2
        ft.rangeUpdate(2, 4, 10); // a[2..4] += 10 → a=[2,12,13,14,5]
        System.out.println(ft.rangeSum(2, 4)); // 输出 12+13+14 = 39
    }
}

关键细节与注意事项

• 下标必须 1-indexed：Fenwick Tree 太依赖 lowbit 了，如果用下标 0 会导致死循环。所以数组长度声明为 n+1，操作时索引从 1 开始，这一点踩坑的人不少。
• 数据类型用 long：避免区间更新时中间乘法溢出（比如 (l−1)×delta），用 long 更安全。
• rangeUpdate 中 r+1 越界检查不能省：不然一不小心就写到了 tree[n+1] 引发 ArrayIndexOutOfBoundsException。
• 单点更新/查询可以复用：比如单点更新 a[i] += v 就是 rangeUpdate(i,i,v)；单点查询 a[i] 就是 rangeSum(i,i)。
• 所有操作的时间复杂度都是 O(log n)，空间 O(n)，用起来很轻快。

对比线段树：什么时候选 Fenwick？

和线段树比起来，Fenwick Range 的实现明显更轻量，代码更短，常数也更小。它特别适合下面这些场景：

• 只需要区间加、区间求和，不涉及赋值、取 max/min、历史版本等复杂操作。
• 离线操作或者强制在线但内存敏感的环境。
• 竞赛场景中追求简洁与速度，Fenwick 往往是首选。

当然，如果你的需求更复杂，比如需要区间赋值、多种标记下传、动态开点，那线段树仍然是更通用的选择。Fenwick 和线段树各有千秋，选哪个，关键看你的数据结构和操作到底有多“单纯”。