树状数组在Python中需用1-indexed实现：初始化时tree长度为n+1，所有操作索引+1；单点修改必须调用update而非直改tree，因需维护位运算父子关系；前缀查询query(i)返回[1..i]和，查[l,r]需query(r+1)-query(l)。
树状数组在Python里怎么初始化才不翻车
Python没有内置树状数组，得自己写；但直接照搬C++模板容易越界或下标错乱，因为Python列表从0开始，而经典树状数组逻辑默认1-indexed。
正确做法是让内部数组长度为 n+1，所有操作都对索引+1处理，避免反复加减。别图省事用0-indexed改逻辑——后面单点更新和前缀查询全会出错。
- 初始化时传入原始数组
a，内部建tree = [0] * (len(a) + 1) - 构造时对每个
i（从0开始），调用update(i + 1, a[i])，不是update(i, a[i]) - 如果原始数组可能为空，提前判断
if not a: return，否则len(a)+1会是1，但后续update(1, ...)仍合法，只是没数据
单点修改为什么必须用 update 而不是直接改 tree
树状数组的结构依赖父子节点的位运算关系（i & -i），直接改 tree[i] 只影响一个位置，破坏了区间和的维护逻辑，后续所有前缀查询都会错。
比如把第5个元素加3，你得从 i = 5 开始，不断跳到 i += i & -i，沿途所有覆盖5的节点都要加3——这是 update 干的事。
立即学习“Python免费学习笔记（深入）”；
-
update(i, delta)中的i是1-indexed位置，传入前记得+1 - delta 是「变化量」，不是新值；要设为新值得先查旧值再算差，一般不这么干
- 别在循环里反复调用
update改同一位置：Python函数调用开销小，但逻辑上没问题；真正慢的是没批量预处理就高频单点改
query(i) 查的是前缀和，不是区间和，别直接套用
query(i) 返回的是 [1..i] 的和（1-indexed），想查 [l, r] 得手动算 query(r) - query(l-1)。很多人漏掉 l-1 导致左端点被多算一次。
更隐蔽的问题是：当 l == 1 时，query(0) 会越界或返回0——所以必须保证 query 函数内部对 i 返回0，不能硬查 <code>tree[0]。
- 标准
query(i)实现里，循环条件是while i > 0，不是>= 1或>= 0 - 查
[l, r]（原数组0-indexed下标）时，对应1-indexed是[l+1, r+1]，所以写query(r+1) - query(l) - 如果频繁查区间和，且修改少、查询多，考虑是否真需要树状数组——前缀和数组更省空间也更快
Python里性能瓶颈往往不在算法逻辑，而在列表访问和循环
纯Python实现的树状数组，在n=1e5、q=1e5时可能比C++慢5–10倍，但通常够用；真正的卡点常是字符串转int、输入读取、或者在 update/query 里写了多余print或list.copy()。
- 避免在循环中调用
sys.stdin.readline().strip().split()多次；一次性读完再解析 -
tree用普通列表就行，别用array.array或numpy——索引开销反而更大，且不兼容位运算逻辑 - 如果题目强制在线、强制单点改+前缀查，且n极大（>1e6），Python树状数组大概率过不了，该换PyPy或C++，别硬优化
最易忽略的一点：树状数组只适用于「支持区间加、支持单点改」的场景，如果要区间修改（比如[l,r]全部加x），它搞不定，得上线段树或差分+树状数组组合——但那是另一个问题了。
