树状数组
进阶树状数组把前缀和拆成若干 lowbit 管辖区间。
// 算法讲解
树状数组
示例会同时展示原数组和 bit 数组，方便理解 lowbit 覆盖区间。
待机
速度 中
待机 ⌨1vector<int> bit;
2
3int lowbit(int x) {
4 return x & -x;
5}
6
7void add(int idx, int delta) {
8 for (int i = idx; i < (int)bit.size(); i += lowbit(i)) {
9 bit[i] += delta;
10 }
11}
12
13int query(int idx) {
14 int sum = 0;
15 for (int i = idx; i > 0; i -= lowbit(i)) {
16 sum += bit[i];
17 }
18 return sum;
19}
复杂度分析
时间 更新/查询 O(log n)
空间 O(n)
最优 O(log n)
最坏 O(log n)
算法讲解
树状数组的核心是 lowbit(x)，它表示索引 x 在二进制中最低位的 1 所对应的贡献范围。
通过不断跳转 x += lowbit(x) 或 x -= lowbit(x)，我们能在 O(log n) 内完成更新和前缀查询。
它代码短、常数小，是竞赛中处理动态前缀和、逆序对、离散化统计的高频工具。
和线段树相比，它更轻量，但功能也更偏向可加性前缀信息。