树状数组的思想复习

树状数组的复习

前言：

学树状数组的时候第一没理解透彻，第二还没写博客用于复习，所以这里写一下用于复习

树状数组：

作用：logn

logn时间实现单点修改区间查询；区间修改单点查询；区间修改区间查询。

但是区间修改区间查询还是线段树好，因为扩展性很强

特点：父子节点关系

例如当前节点为x，那么fa[x]=x+lowbit(x);

做题方法

1.单点修改区间查询

a[i]表示原数组，t[i]表示前缀数组，然后在x<=n的范围内不断地+lowbit(x)更新父亲的t数组即可

那怎么查询呢，

先来个特殊的，1-x的查询，例如x=7时，sum[7]=t[7]+t[6]+t[4] ,我们进一步发现,6=7-lowbit(7),4=6-lowbit(6)，所以我们可以通过不断的-lowbit操作来实现求和

那么一段区间的就求差就行了

2.区间修改单点查询

原数组a[i]，a[i]差分数组b[i]，用上面的方法维护两次单点修改的b数组即可

模板：P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[500005];
int t[500005];
int lowbit(int x){
	return x&(-x);
}
void add(int x,int val){
	for(int i=x;i<=n;i+=lowbit(i)){
		t[i]+=val;
	}
}
int ask(int x){
	int ret=0;
	for(int i=x;i>=1;i-=lowbit(i)){
		ret+=t[i];
	}
	return ret;
}
signed main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		add(i,a[i]);
	}
	while(m--){
		int a,b,c;
		cin >> a >> b >> c;
		if(a==1){
			add(b,c);
		}
		else{
			cout<<ask(c)-ask(b-1)<<endl;
		}
	}
}
	

区间修改单点查询不也EZ？https://www.luogu.com.cn/record/112034120

练习题详见铃狐sama的竞赛复习计划 - 铃狐sama - 博客园 (cnblogs.com)