树状数组：用 lowbit 拼出前缀和

先理解：tree[i] 到底维护哪一段？

lowbit(i) 表示二进制下最低位的 1 对应的值。它决定了 tree[i] 负责的区间长度。

例如 i=6，二进制是 110，所以 lowbit(6)=2，于是 tree[6] 维护 [5,6]。

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

单点加：为什么是 i += lowbit(i)？

当 a[x] 增加 k 时，所有“包含 x 的 tree 区间”都要更新。沿着 x, x+lowbit(x), ... 往上跳，刚好会经过这些负责区间。

void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += k;
    }
}

前缀查询：为什么是 i -= lowbit(i)？

查询 query(x) 时，我们把 [1,x] 拆成若干个 tree 已经维护好的区间。从 x 开始，每次拿走 tree[i] 负责的一段，然后跳到左边剩余部分。

int query(int x) {
    int ans = 0;
    for (int i = x; i; i -= lowbit(i)) {
        ans += tree[i];
    }
    return ans;
}

区间加 + 单点查询：维护差分数组

如果树状数组里维护的是差分数组 d[i] = a[i] - a[i-1]，那么 a[x] 就等于 d[1] + ... + d[x]。

于是给区间 [l,r] 整体加 k，只需要让 d[l] += k，再让 d[r+1] -= k。查询单点值时，直接求差分前缀和。

add(i, a[i] - a[i - 1]);
void range_add(int l, int r, int k) {
    add(l, k);
    add(r + 1, -k);
}
int point_query(int x) {
    return query(x);
}