区间查询数据结构 · HTML
数学 / 逻辑形态
支持 add(i,delta) 与 prefix(r)=aggregate(a[0:r])；区间由两个前缀相消。
识别信号
- 点更新与区间查询在线交错
- 查询可转为前缀聚合
- 聚合存在可逆操作
- 离散化后统计频次或秩
- 希望比线段树更短且常数小
容易误判的相似信号
| Signal | Why it is different |
|---|
| 复杂区间赋值 | 基础 Fenwick 不自然支持；考虑 lazy segment tree。 |
| 不可逆动态聚合 | 动态区间最小值不能由两个前缀相消，应选 segment tree。 |
核心不变量
1-based tree[i] 保存 (i-lowbit(i),i] 的聚合；查询下降链把前缀拆成互不重叠块。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 长度 n+1 的 tree；对外 0-based，下标进入结构时加一。 |
| Transition | add 反复 i+=lowbit(i) 更新祖先块；prefix 反复 i-=lowbit(i) 收集分解块。 |
| Frontier / order | 更新前沿向更大祖先块移动；查询前沿清除最低有效位直至 0。 |
Python 骨架
class Fenwick:
def __init__(self, n):
self.n = n
self.t = [0] * (n + 1)
def add(self, index, delta):
i = index + 1
while i <= self.n:
self.t[i] += delta
i += i & -i
def prefix(self, right):
total, i = 0, right
while i:
total += self.t[i]
i -= i & -i
return total
def range_sum(self, left, right):
return self.prefix(right) - self.prefix(left)
正确性思路
- lowbit 唯一决定每个 tree 单元覆盖的块。
- add 访问恰好所有包含该点的块。
- prefix 的下降链互不重叠且完整覆盖目标前缀。
- 两个前缀相消后只剩 [left,right)。
复杂度
| Time | Space | Parameters |
|---|
| 更新、前缀和、区间和均 O(log n) | O(n) | n 为数组长度；逐点构建为 O(n log n) |
边界条件
- prefix 使用右开边界
- 空区间返回 0
- 内部必须 1-based
- 赋值要转换成 delta
- 离散化相同值映射同秩
错误模式
| Pattern | Why it fails / fix |
|---|
| 从内部下标 0 更新 | lowbit(0)=0 会死循环。 |
| 端点错一位 | 统一 prefix(r) 为 [0,r)。 |
| 把 set 当 add | 设置新值需添加 new-old。 |
选择与排除规则
- 点加加前缀或区间和：Fenwick。
- 复杂聚合或区间更新：segment tree。
- 完全静态：prefix sum 或 sparse table。
- 秩统计先离散化再明确严格或非严格前缀。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 新区间和为 8。 |
| Scenario | 数组 [2,0,3,1]，下标 1 增加 4，再查询 [1,4)。 |
| Walkthrough | add 更新所有含第二项的块；prefix(4)-prefix(1)=10-2。 |
Recall prompts
我的补充