这题用区间查询+区间修改的方法过得了吗?
查看原帖
这题用区间查询+区间修改的方法过得了吗?
233957
190040257a楼主2020/8/12 19:25

蒟蒻刚学完树状数组,用区间查询+区间修改的方法TIE了后面两个点,想问一下这题是不是只能用区间修改+单点查询的方法。 附上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long  sum1[503030];
long long  sum2[504024];
int a[503030];
int N,M;
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int k)
{
	int xx=x;
	while(x<=N)
	{
		sum1[x]+=k;
		sum2[x]+=(xx-1)*k;
		x+=lowbit(x);
	}
}
long long search(int x)
{
	long long s=0;
	int i=x;
	while(x>0)
	{
		s+=i*sum1[x]-sum2[x];
		x-=lowbit(x);
	}
	return s;
	
}
long long ask(int l,int r)
{
	return search(r)-search(l-1);
}
int main()
{
	cin>>N>>M;
	for(int i=1;i<=N;i++)
	{
		cin>>a[i];
		add(i,a[i]-a[i-1]);
	}
	for(int i=1;i<=M;i++)
	{
		int z,l,r,k;
		int x;
		cin>>z;
		if(z==1) 
		{
			cin>>l>>r>>k;
			add(l,k);
			add(r+1,-k);
		}
		if(z==2)
		{
			cin>>x;
			cout<<ask(x,x)<<endl;
		}
	}
	return 0;
}
2020/8/12 19:25
加载中...