关于树状数组的问题
  • 板块学术版
  • 楼主GuoJZ2010
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/7 11:34
  • 上次更新2024/1/7 14:35:38
查看原帖
关于树状数组的问题
513005
GuoJZ2010楼主2024/1/7 11:34

树状数组的图是这样吗?

如果是,按照此P3368模板题AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t[501000],n,m;
int lowbit(int a){
	return a&-a;
}
void add(int x,int b){
	while(x<=n){
		t[x]+=b;
		x+=lowbit(x);
	}
}
int one_dfs(int x){
	int sum=0;
	while(x!=0){
		sum+=t[x];
		x-=lowbit(x);
	}
	return sum;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
	    int l;
		cin>>l;
		add(i,l);
		add(i+1,-l);
	}
	for(int i=1;i<=m;i++){
		int a;
		cin>>a;
		if(a==1){
			int x,y,k;
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
	//		for(int i=1;i<=5;i++) cout<<t[i]<<" ";
	//		cout<<endl;
		}
		if(a==2){
			int x;
			cin>>x;
			cout<<one_dfs(x)<<endl;
		}
	}
	return 0;
}

实现区间修改,在1-2间+k

按照查分,1,2,4,8会+k

2+1=3,在3,4,8会-k

t[3]是不是多-k了?

2024/1/7 11:34
加载中...