动态开点の线段树

因为静态建点线段树消耗的空间太大了，需要开四倍空间，但是动态开点就可以大大降低所使用的空间，远小于四倍

具体思想和线段树没有区别只是将\(k<<1\)换成了\(LS(k)\)，将\(k<<1|1\)换成了\(RS(k)\)，（具体开多少空间不是很能确定

#include <cstdio>
#include <iostream>
#define LS(x) tree[x].ls
#define RS(x) tree[x].rs
#define L(x) tree[x].l
#define R(x) tree[x].r
typedef long long LL;
using namespace std;
const int maxn = 2e5+6;
int n,m,ncnt = 1;
LL ans = 0;
struct Tree{
	int l,r,ls,rs;
	LL sum,tag;
}tree[maxn];

void build(int p,int v,int k)
{
	if(L(k) == R(k))
	{
		tree[k].sum = v;
		return ;
	}
	int mid = L(k) + R(k) >> 1;
	if(p <= mid)
	{
		if(!LS(k)) LS(k) = ++ ncnt;
		L(LS(k)) = L(k);
		R(LS(k)) = mid;
		build(p,v,LS(k));
	}
	else {
		if(!RS(k)) RS(k) = ++ ncnt;
		L(RS(k)) = mid + 1;
		R(RS(k)) = R(k);
		build(p,v,RS(k));
	}
	tree[k].sum = tree[LS(k)].sum + tree[RS(k)].sum;
	return ; 
}

void down(int k)
{
	tree[LS(k)].sum += (R(LS(k)) - L(LS(k)) + 1) * tree[k].tag;
	tree[RS(k)].sum += (R(RS(k)) - L(RS(k)) + 1) * tree[k].tag;
	tree[LS(k)].tag += tree[k].tag;
	tree[RS(k)].tag += tree[k].tag;
	tree[k].tag = 0;
	return ;
}

void update(int l,int r,int v,int k)
{
	if(l <= L(k) && R(k) <= r)
	{
		tree[k].sum += (R(k) - L(k) + 1) * v;
		tree[k].tag += v;
		return ;
	}
	if(tree[k].tag) down(k);
	int mid = L(k) + R(k) >> 1;
	if(l <= mid) update(l,r,v,LS(k));
	if(r > mid) update(l,r,v,RS(k));
	tree[k].sum = tree[LS(k)].sum + tree[RS(k)].sum;
	return ;
}

void query(int l,int r,int k)
{
	if(l <= L(k) && R(k) <= r)
	{
		ans += tree[k].sum;
		return ;
	}
	if(tree[k].tag) down(k);
	int mid = L(k) + R(k) >> 1;
	if(l <= mid) query(l,r,LS(k));
	if(r > mid) query(l,r,RS(k));
	return ;
}

int main()
{
	scanf("%d%d",&n,&m);
	L(1) = 1,R(1) = n;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		build(i,x,1);
	}
	while(m --)
	{
		int op;
		scanf("%d",&op);
		if(op == 1)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			update(x,y,z,1);
		}
		else {
			int x,y; ans = 0;
			scanf("%d%d",&x,&y);
			query(x,y,1);
			printf("%lld\n",ans);
		} 
	}
	return 0;
}