树状数组（fenwick tree）可通过双数组结合差分实现区间更新与区间查询，核心是维护d[i]和(i−1)·d[i]，时间复杂度o(log n)，适用于仅需区间加和求和的轻量场景。
Java 中没有“二进制扇形树”这个标准术语，您实际想表达的是 树状数组（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]
Java 实现：支持区间更新与区间查询的 Fenwick Tree
以下为完整、可运行的 Java 数组实现（1-indexed，下标从 1 开始）：
class FenwickRange {
private long[] tree1;
private long[] tree2;
private int n;
<pre class="brush:java;toolbar:false;">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 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 <p>}</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill9868" title="Java注释规范Skills"><img
src="https://img.php.cn/upload/skill/001/246/273/6adaf20dbae7c507.jpg" alt="Java注释规范Skills" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill9868" title="Java注释规范Skills" class="overflowclass">Java注释规范Skills</a>
<p class="overflowclass">当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。</p>
</div>
<a rel="nofollow" href="/xiazai/skill9868" title="Java注释规范Skills" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>使用示例：
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）
- 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、历史版本等）
- 离线操作或强制在线但内存敏感
- 竞赛中追求简洁与速度
若需支持更多操作（如区间赋值、多种标记下传、动态开点），线段树仍是更通用的选择。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
