线段树（On2）

#include<bits/stdc++.h>
using namespace std;
typedef struct{
	int l,r,w;
}Node;
Node nodes[1000000]={0,0,0};
int x,y,ans,mod,single;
void build(int l,int r,int n)
{//建树
	nodes[n].l=l;nodes[n].r=r;
	if(nodes[n].l==nodes[n].r)
	{
		scanf("%d",&nodes[n].w);
		return;
	}
	build(l,(l+r)/2,n*2);
	build((l+r)/2+1,r,n*2+1);
	nodes[n].w=nodes[n*2+1].w+nodes[n*2].w;
}
void singleSearch(int k)
{//单点查询
	if(nodes[k].l==nodes[k].r)
	{
		printf("%d",nodes[k].w);
		return;
	}
	int mid=(nodes[k].l+nodes[k].r)/2;
	if(single<=mid)singleSearch(k*2);
	else singleSearch(k*2+1);
}
void singleChange(int k)
{//单点修改
	if(nodes[k].l==nodes[k].r)
	{
		nodes[k].w+=mod;
		return;
	}
	int mid=(nodes[k].l+nodes[k].r)/2;
	if(single<=mid)singleChange(2*k);
	else singleChange(2*k+1);
	nodes[k].w+=mod;
	//nodes[k].w=nodes[2*k].w+nodes[2*k+1].w;
}
void partSearch(int k)
{//区间查询
	if(nodes[k].l>=x&&nodes[k].r<=y)
	{
		ans+=nodes[k].w;
		return;
	}
	int mid=(nodes[k].l+nodes[k].r)/2;
	if(x<=mid)partSearch(k*2);//左
	if(y>mid)partSearch(k*2+1);//右
}
void partChange(int k)
{//区间修改(不用懒节点)
	if(nodes[k].l>=x&&nodes[k].r<=y)
	{
		if(nodes[k].l==nodes[k].r)
			nodes[k].w+=mod;//到达根节点
		else 
		{//结合建树和向下查询
			partChange(k*2);
			partChange(k*2+1);
			nodes[k].w=nodes[2*k].w+nodes[2*k+1].w;
		}
		return ;
	}
	int mid=(nodes[k].l+nodes[k].r)/2;
	if(y>mid)
		partChange(k*2+1);//左树
	if(x<=mid)
		partChange(k*2);//右树
	nodes[k].w=nodes[2*k].w+nodes[2*k+1].w;
}
void print (int n)
{
	for(int i=1;i<2*n;i++)
		cout<<nodes[i].w<<" | "<<nodes[i].l<<" - "<<nodes[i].r<<endl;
}
int main()
{
	int m,n;cin>>n>>m;
	build(1,n,1);
	//print(n);
	for(int i=0;i<m;i++)
	{
		int op;cin>>op;
		if(op==1)
		{
			cin>>x>>y>>mod;
			partChange(1);
			//print(n);
		}
		if(op==2)
		{
			cin>>x>>y;
			partSearch(1);
			cout<<ans<<endl;
			ans=0;
		}
	}
	return 0;
}