P3368 【模板】树状数组 2 树状数组题解

P3368 【模板】树状数组 2
由于差分数组的前缀和，为原数组的值，用树状数组去维护原数组的差分数组，区间[l,r]修改为t[l]+=delta，t[r+1]-=delta，单点s的查询变成区间[1-s]查询，变成求[1-s]的前缀和。

//P3368【模板】树状数组 2
//P3374 【模板】树状数组 1
#include
using namespace std;
const int Maxn=500000;
typedef long long LL;
LL c[Maxn+1];
LL n,m,pre=0;
int lowbit(int x)
{
	return x&(-x);
}
LL getsum(int x)
{
	LL sum=0;
	while (x>0)
	{
		sum+=c[x];
		x=x-lowbit(x);
	}
	return sum;
}
void add(int x,LL y)
{
	while (x<=n)
	{
		c[x]+=y;
		x+=lowbit(x);
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		LL x;
		scanf("%lld",&x);
		add(i,x-pre);
		pre=x;
	}
	for (int i=1;i<=m;i++)
	{
		LL op,x,y,k;
		scanf("%lld",&op);
		if (op==1)
		{
			scanf("%lld %lld %lld",&x,&y,&k);
			add(x,k);
			add(y+1,-k);
		}
		else
		{
			scanf("%lld",&x);
			printf("%lld\n",getsum(x));
		}
	}
}
/*
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
*/