算法学习：树状数组

核心思想

树状数组本质上是：
用数组模拟一棵隐式的二叉树，每个节点维护一段区间的和。

普通前缀和：a1 a2 a3 a4 a5 a6 a7 a8

前缀和数组：

s1 = a1
s2 = a1+a2
s3 = a1+a2+a3

问题：如果 a3 改变，需要 更新很多位置 → O(n)

树状数组解决方式：把区间拆成不同长度的块进行存储。

位置	维护区间
1	[1,1]
2	[1,2]
3	[3,3]
4	[1,4]
5	[5,5]
6	[5,6]
7	[7,7]
8	[1,8]

每个节点维护一个 长度为 lowbit(i) 的区间[i - lowbit(i) + 1 , i]。

例如：i = 6, lowbit(6) = 2
区间:[6-2+1 , 6]=[5 , 6]

关键函数：lowbit

树状数组最核心的一行代码：
lowbit(x) = x & (-x)
作用：取二进制中最低位的1

例子：

x	二进制	lowbit
6	110	2
8	1000	8
12	1100	4

前缀和查询

查询：

sum(1..x)

方法：

不断 跳父节点

while(x > 0){
    sum += tree[x]
    x -= lowbit(x)
}

示例：
求 sum(7)
7 -> 6 -> 4 -> 0

累加区间：
[7,7]
[5,6]
[1,4]

合起来就是：[1,7]

时间复杂度：O(log n)

单点修改

如果：a[x] += v

需要更新所有 包含x的区间

代码：

while(x <= n){
    tree[x] += v
    x += lowbit(x)
}

例如更新：

x = 3

更新路径：3 -> 4 -> 8 -> 16 …

因为这些节点维护的区间都包含 3

完整代码

int tree[N];
int n;

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

void add(int x,int v){
    while(x <= n){
        tree[x] += v;
        x += lowbit(x);
    }
}

int sum(int x){
    int res = 0;
    while(x > 0){
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}

区间修改

void range_add(int l,int r,int v){
    add(l, v);
    add(r+1, -v);
}

单点查询

int query(int x){
    return sum(x);
}

例子

初始：
a: 0 0 0 0 0
操作：
[2,4] + 3

差分修改：

d[2] += 3
d[5] -= 3

查询：
a[3] = sum(3)

计算：
d: 0 3 0 0 -3

前缀和：
a: 0 3 3 3 0

复杂度

操作	复杂度
区间修改	O(log n)
单点查询	O(log n)

---

为啥查-lowbit，改是+Lowbit

为什么查询要 x -= lowbit(x)：每次减 lowbit，就是跳到“前一个区间”
为什么修改要 x += lowbit(x)：所有包含3的区间都要更新

一句话记忆
查：往左跳区间 x -= lowbit(x)
改：往右跳父节点 x += lowbit(x)

Donate