树状数组天然支持范围求和查询，通过两次前缀和相减实现；但不支持区间最值查询，因最大值无逆元；Python实现需注意1-based存储、0-based接口转换及离散化处理。
树状数组本身不直接支持范围查询？先厘清概念
树状数组（Fenwick Tree）原生只支持单点更新 + 前缀和查询（即 query(i) 返回 arr[0..i] 的和），但「范围查询」如 sum(l, r) 可以通过两次前缀和相减得到：query(r) - query(l-1)。所以它**天然支持范围求和查询**，无需改造结构——关键在于你是否正确实现了前缀和接口，以及是否处理了边界（比如 l=0 时 query(-1) 要返回 0）。
Python 实现中容易出错的三个细节
用 Python 写 Fenwick Tree 时，下标习惯和负索引容易引发隐性 bug：
- 务必使用 1-based 索引内部存储：即
tree[1]对应原数组第 0 个元素，避免0 & -0运算崩溃 -
query(i)中的i是原数组的右闭下标（0-based），内部要转成i+1后再进循环；否则query(0)会跳过更新 -
update(i, delta)同理：传入 0-based 下标i，内部从idx = i + 1开始向上更新
示例片段：
class Fenwick:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1) # 1-based
<pre class='brush:python;toolbar:false;'>def update(self, i, delta): # i is 0-based
idx = i + 1
while idx <= self.n:
self.tree[idx] += delta
idx += idx & -idx
def query(self, i): # sum of arr[0..i], i is 0-based
if i < 0:
return 0
res = 0
idx = i + 1
while idx:
res += self.tree[idx]
idx -= idx & -idx
return res
def range_sum(self, l, r): # l, r are 0-based, inclusive
return self.query(r) - self.query(l - 1)想查区间最值？别硬改树状数组
树状数组的更新/查询逻辑依赖「可逆运算」（如加法有减法逆元），而最大值（max）没有通用逆元——max(a,b,c) - max(a,b) 无法还原 c。所以：
立即学习“Python免费学习笔记（深入）”；
- 不要尝试用标准 Fenwick Tree 支持
range_max或range_min - 需要区间最值，请换用线段树（Segment Tree）或 Sparse Table（静态场景）
- 若坚持用类树状结构，可考虑 Binary Indexed Tree for RMQ，但它仅支持点更新 + 区间查询，且实现复杂、常数大，Python 中性能反而不如朴素遍历小数组
动态开点 or 离散化？看输入规模再决定
原始 Fenwick Tree 要求数组长度已知且固定。遇到坐标很大但实际修改点稀疏的情况（例如更新位置 10**9），不能直接开 [0] * (10**9 + 1)：
- 离散化是首选：收集所有出现过的下标（含查询和更新的
l,r,i），排序去重后映射到0..m-1，再建大小为m的树状数组 - 动态开点（字典模拟树）可行但不推荐：用
dict存非零节点，虽省空间，但每次query需要沿路径检查键是否存在，逻辑臃肿且失去 O(log n) 稳定性 - Python 中若
n <= 10**5，直接离散化 + 标准实现足够快；超过10**6才需谨慎压常数（比如用array.array('i')替代list）
离散化核心就两行：xs = sorted(set(all_positions))，然后用 bisect_left(xs, x) 查坐标。
树状数组的“范围查询”本质是前缀和差分，不是结构扩展；真正卡住人的永远是下标转换和离散化时机——写完先用 l=0, r=0 和 l=0, r=n-1 两个极端 case 跑一遍。
