python中树状数组需手写实现，核心是lowbit运算与1-based索引；初始化长度为n+1，update/query参数为逻辑位置1~n；区间和用query(r)-query(l-1)；大坐标或负数必须先离散化。
树状数组在Python中必须自己实现
Python标准库没有内置的树状数组（Fenwick Tree），list或array无法直接支持 O(log n) 的单点更新 + 前缀和查询。你得手写一个类，核心是利用整数的二进制低位（lowbit）做跳转。别想用numpy或bisect替代——它们不满足动态更新+前缀和同时高效的约束。
常见错误是把索引从 0 开始：树状数组逻辑依赖 1-based 索引，否则lowbit计算和循环会错位。初始化时数组长度要设为 n + 1，下标 0 永远不用。
def lowbit(x):
return x & -x
<p>class FenwickTree:
def <strong>init</strong>(self, n):
self.n = n
self.tree = [0] * (n + 1) # 1-indexed</p><pre class="brush:python;toolbar:false;">def update(self, i, delta):
while i 0:
s += self.tree[i]
i -= lowbit(i)
return s
update 和 query 的参数必须是正整数索引
传给update(i, delta)的i不是 Python 列表下标，而是逻辑位置（1 ~ n）。如果你有一组原始数据arr = [3, 1, 4, 1, 5]，想更新第 3 个元素（即值为 4 的那个），调用的是fenw.update(3, new_val - old_val)，不是fenw.update(2, ...)。
容易踩的坑：
- 误把原始数组下标直接传入，导致越界或漏加
- 在
query(i)中传入 0 —— 会无限循环（因为i -= lowbit(i)在 i=0 时仍是 0） - 更新时没算增量
delta，而是直接赋值，破坏了树状数组的累加结构
区间和要用两次 query 相减
树状数组原生只支持前缀和query(i)，求区间[l, r]和必须写成query(r) - query(l-1)。注意这里的l和r仍是 1-based 位置。
如果原始需求是「实时获取前 k 个元素的和」，就直接用query(k)；如果是「第 3 到第 7 个元素之和」，就得写query(7) - query(2)。
性能上，两次query仍是 O(log n)，不会退化。但别试图合并成一个函数去“优化”——底层跳转路径不同，硬合并没有意义。
离散化是处理大坐标/负数的必要前置
树状数组要求索引是紧凑的正整数（1 ~ n）。如果原始操作的位置是年份（如 1999、2024）、ID（如 1000000007）、或者含负数（如 -5、0、3），必须先离散化。
做法很简单：收集所有出现过的坐标 → 排序 → 去重 → 映射为 1, 2, 3…
coords = sorted(set([1999, 2024, 2001, 1999]))
rank = {v: i+1 for i, v in enumerate(coords)} # {1999:1, 2001:2, 2024:3}
fenw = FenwickTree(len(rank))
fenw.update(rank[2024], 100)
漏掉离散化会导致数组开太大（内存炸）或索引非法（IndexError）。尤其当输入是字符串 ID 或浮点时间戳时，不映射根本没法用。
树状数组的边界感很关键：它不存原始值，只维护差分累加结构；所有接口都假设你清楚自己在操作哪个逻辑位置；离散化不是可选项，是使用前提。写错一次lowbit或索引偏移，整个结果就全偏了，且很难 debug。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
