线段树
除了最后一层满二叉树，用堆（一维数组）来存树，一般来说，开4n的空间
build（int u, int l, int r）
将一段区间初始化为线段树
push up（）
由子节点更新父节点的信息
push down（）（懒标记）
把信息递归的更新到两个子节点
modify（）/ update()
u为结点编号，更新该结点的区间最大值
修改--单点修改or区间修改（懒标记）
quary（int u,int l,int r）
查询某段区间的信息
查询以u为节点，区间l,r中的最大值
luogu P3372 【模板】线段树 1
#include<iostream>
using namespace std;
#define endl "\n"
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)s
const int N=1e5+10;
#define lc p<<1
#define rc (p<<1)+1
int w[N];
struct node
{
int l,r,sum,add;//add->lazy tag
}tr[N*4];
void build(int p,int l,int r)
{
tr[p]={l,r,w[l],0};//sum在回溯时更新，暂时无意义
if(l==r)return;//r如果是叶子节点，返回
//不是叶子节点，分裂
int m=l+r>>1;
build(lc,l,m);
build(rc,m+1,r);
tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void pushup(int p)
{//向上更新
tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int p)
{//向下更新
if(tr[p].add)
{
tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1);
tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1);
tr[lc].add+=tr[p].add;
tr[rc].add+=tr[p].add;
tr[p].add=0;
}
}
void update(int p,int x,int y,int k)
{//p父节点编号 xy区间 k修改的值
if(x<=tr[p].l&&y>=tr[p].r)//覆盖
{
tr[p].sum+=k*(tr[p].r-tr[p].l+1);
tr[p].add+=k;
return;
}
//不覆盖
int m=tr[p].l+tr[p].r>>1;
pushdown(p);
if(x<=m)update(lc,x,y,k);
if(y>m)update(rc,x,y,k);
pushup(p);
}
int quary(int p,int x,int y)
{
if(x<=tr[p].l&&tr[p].r<=y)
return tr[p].sum;
int m=tr[p].l+tr[p].r>>1;
pushdown(p);
int sum=0;
if(x<=m)sum+=quary(lc,x,y);
if(y>m)sum+=quary(rc,x,y);
return sum;
}
void solve()
{
int n,q;
cin>>n>>q;
rep(i,1,n)cin>>w[i];
build(1,1,n);
while(q--)
{
int nn;
cin>>nn;
if(nn==1)
{
int x,y,k;
cin>>x>>y>>k;
update(1,x,y,k);
}
if(nn==2)
{
int x,y;
cin>>x>>y;
cout<<quary(1,x,y)<<endl;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
//cout<<"123"<<endl;
solve();
}