因为for循环区间求和O(n)无法应对高频查询或修改，树状数组（单点改+区间和）和线段树（支持区间更新、最值等复杂操作）通过预处理将查询/更新优化至O(log n)。
为什么区间求和不用 for 循环累加？
直接遍历 arr[l] 到 arr[r] 求和，时间复杂度是 O(n)。当有大量查询（比如 10⁵ 次）或数组频繁修改时，总耗时会爆炸。这时需要预处理结构——树状数组（Fenwick Tree）和线段树（Segment Tree）就是为此而生的两个主流选择。
std::vector 上手写树状数组：5 步实现单点更新 + 区间查询
树状数组代码短、常数小、易调试，适合只涉及「单点修改 + 区间求和」的场景。注意它下标必须从 1 开始，实际使用时常把原数组整体右移一位。
- 定义
tree数组大小为n + 1（n是原数组长度） -
lowbit(x)写成x & -x，别用循环或pow - 更新操作：
void add(int i, int delta)，从i开始向上跳i += lowbit(i) - 前缀和查询：
int sum(int i)，从i向下跳i -= lowbit(i) - 区间
[l, r]求和 =sum(r) - sum(l-1)，注意l是原数组下标（已转为 1-indexed）
int n = arr.size();
vector<long long> tree(n + 1, 0);
<p>auto lowbit = [](int x) { return x & -x; };</p><p>auto add = [&](int i, int delta) {
while (i <= n) {
tree[i] += delta;
i += lowbit(i);
}
};</p><p>auto sum = [&](int i) -> long long {
long long res = 0;
while (i > 0) {
res += tree[i];
i -= lowbit(i);
}
return res;
};</p><p>// 初始化：对每个位置 i（原下标 0 → 新下标 1）
for (int i = 0; i < n; ++i) {
add(i + 1, arr[i]);
}</p><p>// 查询 [l, r]（原下标，闭区间）
long long range_sum = sum(r + 1) - sum(l);</p>线段树更适合什么场景？
当你不止要区间求和，还要支持「区间赋值」「区间加法」「最大值/最小值查询」「混合操作」时，线段树更灵活。但它代码长、内存开销大（约 4 * n）、容易写错边界。
立即学习“C++免费学习笔记（深入）”；
- 必须用数组模拟树：根节点下标为 1，左子节点是
2 * rt，右子是2 * rt + 1 - 懒标记（
lazy）不是可选优化，而是支持区间更新的必要设计 - 建树、查询、更新都要递归，终止条件是当前区间完全落在查询/更新范围内
- 每次查询或更新后，记得在回溯时
push_up（合并子节点结果） - 如果只做单点更新，可以省略
lazy，但区间更新不加lazy会退化成O(n)
树状数组 vs 线段树：几个关键差异点
别盲目套模板。选错结构会让调试时间翻倍。
- 空间：树状数组仅需
O(n)，线段树至少O(4n)，内存紧张时树状数组优势明显 - 编码成本：树状数组核心逻辑 20 行内可写完；线段树带懒标记通常 > 80 行，且
push_down和push_up顺序极易出错 - 扩展性：树状数组难以支持区间最值、历史版本、二维扩展；线段树可改造成可持久化、动态开点、ZKW 形式等
- 常数性能：同为区间求和，树状数组实测快 30%~50%，尤其在高频查询场景
真正容易被忽略的是：树状数组不能直接查区间最值，也不能高效支持「第 k 小」这类顺序统计问题——这时候哪怕多写 100 行，也得切到线段树或平衡树。
