水平有限，前缀和的前缀和什么的，rbq

两个操作：

1.区间l到r加上一个数x

2.查询区间[l,r]的区间和

#include<iostream>

#include<cstdio>

using namespace std;

int n,m,d,x,pt,ptl,ptr;//pt,ptl,ptr我也不知道应该叫什么，类似标记？

long long tree[100000*4+2],pls[100000*4+2],ans;//pls为累加标记

inline void add(int l,int r)

{

	l=l+d,r=r+d;

	pt=0;

	pls[l]+=x,tree[l]+=x;

	if(l!=r)

	{

		pls[r]+=x,tree[r]+=(x<<pt);

		while((l^1)!=r)

		{

			if(!(l&1))

				pls[l^1]+=x,tree[l^1]+=(x<<pt);

			if(r&1)

				pls[r^1]+=x,tree[r^1]+=(x<<pt);

			pt++;

			l=l>>1,r=r>>1,tree[l]=tree[l<<1]+tree[l<<1|1]+(pls[l]<<pt),tree[r]=tree[r<<1]+tree[r<<1|1]+(pls[r]<<pt);

		}

	}

	while(l>>=1)

	{

		pt++;

		tree[l]=tree[l<<1]+tree[l<<1|1]+(pls[l]<<pt);

	}

}

long long getans(int l,int r)

{

	l=l+d,r=r+d;

	ans=tree[l];

	ptl=pt=1;

	if(l!=r)

	{

		ans+=tree[r],ptr=1;

		while((l^1)!=r)

		{

			if(!(l&1))

				ans+=tree[l^1],ptl=ptl+pt;

			if(r&1)

				ans+=tree[r^1],ptr=ptr+pt;

			pt=pt<<1;

			l=l>>1;

			r=r>>1;

			ans=ans+pls[l]*ptl+pls[r]*ptr;

		}

		ptl+=ptr;

	}

	while(l>>=1)

		ans+=pls[l]*ptl;

	return ans;

}

int main()

{

	scanf("%d%d",&n,&m);

	d=1;

	while(d<n)

		d<<=1;

	d--;

	for(int i=1;i<=n;i++)

		scanf("%lld",&tree[d+i]);

	for(int i=(n+d)>>1;i;i--)

		tree[i]=tree[i<<1]+tree[i<<1|1];

	int t,l,r;

	while(m--)

	{

		scanf("%d%d%d",&t,&l,&r);

		if(t==1)

		{

			scanf("%d",&x);

			add(l,r);

		}

		else

			printf("%lld\n",getans(l,r));

	}

	return 0;

}