核心概述：树状数组（Fenwick Tree）支持单点增量更新与前缀和查询，含按和找位置的 lower_bound，所有操作均为 O(log N)。
原文引述：
Description: Computes partial sums a[0] + a[1] + … + a[pos - 1], and updates single elements a[i], taking the difference between the old and new value. Time: Both operations are . Status: Stress-tested
展开阐述：
- 定义与问题背景、适用场景
- 用于维护一维数组的前缀和，支持频繁的点更新与区间前缀查询，在在线计数、秩统计、离散化后的频率统计等场景广泛适用。
- 接口与数据结构字段
- 内部：一维数组 s 存每个低位块的累加值，基于二进制最低位分块思想。
- update(pos, dif)：将 a[pos] 增加 dif（传入“差值”，非直接赋值）。
- query(pos)：返回前缀和 sum([0, pos))，半开区间。
- lower_bound(sum)：返回最小的 pos 使前缀和 ≥ sum；sum ≤ 0 返回 -1；若从未达到则返回 n。
- 核心算法流程/要点
- update：for (; pos < sz(s); pos |= pos + 1) s[pos] += dif
- 利用 pos |= pos + 1 跳至包含该点的更大块，逐层累加。
- query：for (; pos > 0; pos &= pos - 1) res += s[pos - 1]
- 逐步去掉最低位 1，累加覆盖块得到前缀和。
- lower_bound：二进制提升，按 2^k 从高到低试探扩展，当试扩后块和仍小于目标时推进并减少目标值。
- update：for (; pos < sz(s); pos |= pos + 1) s[pos] += dif
- 复杂度与边界条件
- 三个操作均为 O(log N)；数组下标多为 0 基或 1 基的实现细节需统一，本文以 query([0,pos))为约定。
- lower_bound 的返回值约定需遵守，以免与业务下标语义冲突。
- 实现细节与坑
- update 使用差值语义，若需“赋值”为 x，应先求 dif = x - 当前值。
- query 是半开区间 [0,pos)，避免 off-by-one。
- lower_bound 需要预先确定最大的探测步长（不小于 n 的最大 2 的幂）。
- 变体/扩展
- 可扩展到二维见 004-数据结构-二维树状数组；若需区间加区间和可考虑差分或线段树 012-数据结构-线段树。
- 正确性要点
- 依赖二进制分块不变式：s[i] 存储覆盖 [i - lowbit(i) + 1 .. i] 的和（按实现的下标约定适配），update/query 分别沿着块父链累加/剥离，保证前缀和一致。