# 讲个识儿 1集·树状数组

3cfb

2026-06-14 14:57:09

发布于：陕西

12阅读

0回复

0点赞

Xp1.树状数组的应用场景

记笔记！

树状数组的询问在O(logN)级别
树状数组的更新在O(logN)级别
树状数组的用途是单点修改
什么意思呢，来看看吧！

树状数组的用途主要是前缀和改进优化

这是普通前缀和

	1	2	3	4	5	6	7	8	9
$a[i]$	5	6	2	3	1	7	6	3	0
$s[i]$	5	11	13	16	17	24	30	33	33

若要修改，过程极其繁琐

如假如我要修改 $a[i]$ 的第6项为9

a[i]修改

s[i]修改

可以看到，以上操作极其繁琐
os:一定会炸......

所以...

Xp2.思路与讲解

树状数组主要是运用2进制拆分达到的

首先我们要明白2进制拆分

因为一个10进制数可以拆分成若干个2的n次幂数
如图

13=1+4+8

当然，其他数也可以

13=1+4+8
12=4+8
20=4+16
22=2+4+16
25=1+8+16
......

所以，我们可以通过这点优化前缀和

/如求s[13]

s[1]=a[1];
s[4]=a[1]+a[2]+a[3]+a[4];
s[8]=a[1]+a[2]+a[3]+a[4]+...+a[8];
s[13]=s[1]+s[4]+s[8];

Xp3.求数并修改

那如何拆分呢？

1101 (13)

1101->
0001 (1)

1100->
0100 (4)

1000->
1000 (8)

0
1+4+8=13;
...
所以，我们发现，拆分数就是把2进制的最后一个1去掉
代码：x&(-x)
修改更加简单
若我要修改 $s[3]$ 项， $n=13$ ，直接修改 $s[4]（a[1]+a[2]+a[3]+a[4]）$ , $s[8]（a[1]+a[2] +a[3]+...+a[8]）$ 不修改 $s[1],s[2],s[16]...$ 因为他们不在3~13范围内

Xp4.实践与代码

可以知道我们需要一个update来进行单点修改，并同时向上递增修改,同时还需要一个sum求解，即l-r的和，根据上述所说，我们只需向下加和，比如l=13,r=3,先-8,再-2即可。更更更同时，还需有一个函数求x&(-x)

lowbit

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

update

我们要向上修改，在2进制中增加次幂即可，也就是+lowbit
x代表要修改的数，n是数组长,y是要改的数

void update(int x,int y){
	for(int i=x;i<=n;i+=lowbit(i)){
		s[i]+=y;
	}
}

sum

我们要不断求和
$eg:s[14]=s[8]+s[4]+s[2]$ 从14向下递减

int sum(int x){
	int Sum=0;
	for(int i=x;i>0;i-=lowbit(i)){
		Sum+=s[i];
	}
    return Sum;
}

也就是树状数组：

Xp5.代码演示

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[512345],s[512345];
int lowbit(int x){
	return x&(-x);
}
void update(int x,int y){
	for(int i=x;i<=n;i+=lowbit(i)){
		s[i]+=y;
	}
}
int sum(int x){
	int Sum=0;
	for(int i=x;i>0;i-=lowbit(i)){
		Sum+=s[i];
	}
    return Sum;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		update(i,a[i]);
	}
	for(int i=1;i<=m;i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1) update(x,y);
		else cout<<sum(y)-sum(x-1)<<'\n';
	}
	return 0;
}