树状数组：
为什么 lowbit 既能向前求和，又能向后更新

求和与修改，两头都要快。

题目要求维护一个整数数组，支持两个操作：把某个位置的数值改成 val，以及查询闭区间 [left, right] 内所有数字之和。

如果用普通数组，单点修改是 O(1)，但每次区间求和都要从头加到尾，是 O(n)；如果用普通前缀和，区间查询是 O(1)，但修改一个数就要把后面所有前缀和都重算一遍，变成 O(n)。当两种操作频繁交替时，任何一种极端都会超时。树状数组（Fenwick Tree）用巧夺天工的二进制分段，让修改和求和都能在 O(log n) 内完成。

向后累加更新，向前跳跃求和。

标准样例 nums = [1, 3, 5, 7, 9]。点击“下一步”，观察原数组如何构建树状数组，以及执行 update 与 sumRange 时各个节点的树形传递过程。

用 lowbit，分出不重不漏的段落。

1. 01

   树下标从 1 开始（1-based）

   树状数组的下标必须从 1 开始，因为 lowbit(0) = 0 会陷入死循环。原数组的 index 进入树状数组必须映射为 index + 1。

2. 02

   lowbit(x) = x & (-x)

   计算机采用补码表示负数，-x = ~x + 1。两者按位与，恰好只保留了二进制中最右侧的那个 1。这个值就是节点 tree[x] 管辖的连续元素个数。

3. 03

   区间和差分：两端前缀和相减

   任意闭区间 [left, right] 的和，等于 prefix(right + 1) - prefix(left)。通过向前跳步求出两个前缀和相减，无需维护复杂区间合并逻辑。

两组循环，搞定向前与向后。

这段代码来自仓库解法。结构体同时维护当前数组与树状数组，add 负责向后传播差值，prefix 负责向前收集前缀和。

int lowbit(int x) {
    return x & -x;
}

/* 向后更新：沿父节点链将 delta 累加至所有包含 index 的区间 */
void add(NumArray *obj, int index, int delta) {
    while (index <= obj->n) {
        obj->tree[index] += delta;
        index += lowbit(index);
    }
}

/* 向前求和：沿二进制不相交区间累加 [1, i] 的前缀和 */
int prefix(NumArray *obj, int i) {
    int sum = 0;
    while (i > 0) {
        sum += obj->tree[i];
        i -= lowbit(i);
    }
    return sum;
}

void numArrayUpdate(NumArray *obj, int index, int val) {
    int delta = val - obj->num[index];
    add(obj, index + 1, delta);
    obj->num[index] = val;
}

int numArraySumRange(NumArray *obj, int left, int right) {
    return prefix(obj, right + 1) - prefix(obj, left);
}

仓库中使用 malloc 分配 n + 1 大小的 tree 数组，并在使用完毕后显式通过 numArrayFree 释放内存。

原复盘里，留下的五个提醒。

这五条真实记录在当时的题目笔记中。树状数组的代码极度精悍，但下标偏差、差值更新和内存管理很容易埋下隐患。

01 结构体需要同时存原数组

更新时需要计算差值 delta = val - oldValue，所以必须保留一份当前真实值的 num 数组，不能以为有了 tree 就能丢掉原数组。

02 建树时不能只开空间不插入

分配完 tree 数组清零后，必须对每个元素调用 add(obj, i + 1, nums[i]) 把初始值插入树中，只复制原数组相当于建了一棵全零树。

03 修改只需定位受影响节点

update 绝不能重新遍历数组重建整棵树。先算差值 delta，更新原数组，再把 delta 单路传给 add，复杂度才是真正的 O(log n)。

04 树下标与前缀和偏移别搞错

index 进入树要加 1；区间 [left, right] 的和对应的是 prefix(right + 1) - prefix(left)，左端点 left 不能再加 1，否则会少扣除第 left 个数。

05 销毁时先释放内层动态数组

在 C 语言中，释放 obj 前必须先释放 obj->num 和 obj->tree，最后再释放 obj 本身，防止内存泄漏。

用几个典型情形，检查边界。

在两个极端之间，找到巧妙的平衡点。

普通数组查询慢（$O(n)$），前缀和数组修改慢（$O(n)$）。树状数组的核心思想是通过二进制的权值拆分，让每个节点只对特定的一部分区间负责，从而让修改和查询均平摊到优雅的 $O(\log n)$。

建树总时间为 O(n log n)，额外空间复杂度为 O(n)。演示模块额外保留历史快照供前后步进。