关于树状数组
  • 板块学术版
  • 楼主pyyyyyy
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/6/24 18:59
  • 上次更新2023/11/7 00:08:27
查看原帖
关于树状数组
122557
pyyyyyy楼主2020/6/24 18:59

区间修改,单点查询

求助,下面的写法为什么不对?

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+2020;
int delta[N],n,q,a[N];
int lowbit(int x) {
	return x&(-x);
}
void add(int x,int val) {
	while(x<=n) delta[x]+=val,x+=lowbit(x);
}
int sum(int r) {
	int ret=0;
	while(r) ret+=delta[r],r-=lowbit(r);
	return ret;
}
signed main() {
//	freopen("P3368_1.in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>q;
	for(int i=1; i<=n; ++i)
	{
		scanf("%lld",&a[i]);
		delta[i]=a[i]-a[i-1];
		add(i,delta[i]);
	}
	while(q--) {
		int opt,l,r,x;
		scanf("%lld",&opt);
		if(opt==1) scanf("%lld %lld %lld",&l,&r,&x),add(l,x),add(r+1,-x);
		else if(opt==2) scanf("%lld",&x),cout<<sum(x)<<'\n';
	}
	return 0;
}
2020/6/24 18:59
加载中...