1. 题目
有一个长度为 n 的动态频率表，位置 i 的值会被频繁增加，系统需要查询前缀和、区间和，并按累计权重找到第 k 个单位落在哪个位置。请实现 Fenwick Tree（Binary Indexed Tree），要求单点更新和前缀查询为 O(log n)，并解释它与普通前缀数组、线段树的取舍。
2. 约束与澄清
- 内部数组使用 1-based 下标；公开接口可以接受 0-based 位置，但必须统一转换一次。
- 更新可以是增量，也可以先计算差值再写入；要明确是否允许负值。
k的排名从 1 开始，只有所有权重非负且总和至少为k时才定义按权重选择。- 先讨论单线程结构；并发更新需要额外锁或分片，不能假设普通整数写入自动形成一致快照。
3. 核心思路
树状数组的第 i 项保存一个连续区间的部分和，区间长度由 lowbit(i) = i & -i 决定。前缀查询不断减去 lowbit，单点更新不断加上 lowbit，因此每次只访问 O(log n) 个数组位置。区间和用两个前缀相减；若初始数组已知，可以用线性传播把每个值累加到其父索引，建树为 O(n)。
4. 参考实现
text
class Fenwick:
init(values):
tree = [0] * (len(values) + 1)
for i from 1 to len(values):
tree[i] += values[i - 1]
parent = i + lowbit(i)
if parent < len(tree):
tree[parent] += tree[i]
add(index0, delta):
i = index0 + 1
while i < len(tree):
tree[i] += delta
i += lowbit(i)
prefixSum(index0Exclusive):
total = 0
i = index0Exclusive
while i > 0:
total += tree[i]
i -= lowbit(i)
return total
rangeSum(left0, right0Exclusive):
return prefixSum(right0Exclusive) - prefixSum(left0)按权重选择时，从最高的二进制步长开始试探：若跳到候选索引后的累计和仍小于 k，就接受该步并减少 k；最后得到的下标加一就是第 k 个单位所在的位置。该操作依赖累计和单调，权重出现负数时不能直接使用。
5. 复杂度与取舍
Fenwick Tree 使用 O(n) 数组，单点增量、前缀和和按权重选择均为 O(log n)；线性建树为 O(n)。它比线段树更紧凑、常数更小，但只能自然表达可逆的前缀聚合，难以直接支持区间最小值、复杂区间更新或保留完整分段信息。若所有数据只读，普通前缀数组查询是 O(1)；若需要频繁更新，Fenwick Tree 才体现价值。
6. 验证与观测
- 对随机数组比较每次
add、prefixSum和rangeSum与朴素数组结果，覆盖空数组、单元素和最大下标。 - 测试全为零、权重很大、累计和恰好等于
k、k超出总和以及非法下标。 - 交叉验证线性建树与逐点
add建树的内部数组和查询结果。 - 对按权重选择生成非负随机权重，逐个
k检查返回位置的前缀和边界；单独拒绝负权重输入。
7. 常见误区
- 混用 0-based 和 1-based 下标，导致位置 0 不更新或最后一个位置越界。
- 把
i & -i当作取负号技巧，却没有解释它表示最低位的二进制块。 - 用 Fenwick Tree 处理带负值的按权重选择，忽略累计和不再单调。
- 更新值直接覆盖树节点，而不是沿更新路径累加 delta。
8. 面试评分点
能解释 lowbit 与区间覆盖
应说明每个树节点保存哪段连续区间，以及查询和更新为何沿 lowbit 路径跳转。
能写出无边界错误的实现
应统一 1-based 内部下标，处理空数组、非法位置和右开区间，并保证更新不会访问数组末端之外。
能推导复杂度与建树方式
应给出查询、更新、选择的 O(log n) 和线性建树的 O(n)，并比较前缀数组与线段树的适用边界。
能识别按权重选择的前提
应指出权重必须非负、累计和必须单调，并用边界测试验证 k 恰好命中、超界和大数情况。