（zhx）线段树 （结构体线段树）
前言
由于退役时间太久，线段树都忘了，好好复习一下，发现许多误点，特意详细的写一下，方便下次复习
使用原因
以前也是用普通的线段树，长啥样忘记了，但是因为zhx线段树特别好理解，并且需要更改的地方非常少，很方便
线段树1，区间加，区间求和
以下代码有详细标注，不xi讲
/*
尝试第一次复建线段树
15:41 start
16:05 end
开始该.....
出现的问题是 m=l+r<<1 乘以 2 而不是 除以 2
第一次提交 成功 RE 原因线段树数组要开到平常的四倍
第二次提交 AC
16:14
*/
#include<bits/stdc++.h>
#define root 1,n,1 //方便调用
#define lson l,m,rt<<1 //注意是 l 不是 1 lson表示左子树
#define rson m+1,r,rt<<1|1//同理右子树
#define int long long
using namespace std;
int a[100009];
int read(){int x;scanf("%lld",&x);return x;}
struct node//结构体线段树
{
int l,r,col,sum;// 分别记录 区间左右端点，加号标记，区间总和
node() {l=r=col=sum=0;}//别忘记初始化
void init(int l_,int r_) {l=l_,r=r_,sum=a[l];}//init函数用来赋予线段树实际意义
}z[400018];//超级注意 线段树的空间大小要比平时大四倍
node operator +(const node &l,const node &r)//从在运算符，方便updata
{
node p;
p.l=l.l,p.r=r.r,p.sum=l.sum+r.sum;//其实就是区间合并
p.col=0;
return p;
}
void color(int rt,int v) {z[rt].col+=v; z[rt].sum+=(z[rt].r-z[rt].l+1)*v;}//加法标记函数，线段树中的常规操作，为防止用时太多，不必讲线段树上对应每一个节点都更新，打个标记，使用时下穿即可。
void push(int rt)//下传标记
{
if (z[rt].col!=0)
{
color(rt<<1,z[rt].col);
color(rt<<1|1,z[rt].col);
z[rt].col=0;//下传后别忘记清零
}
return;
}
void update(int rt) {z[rt]=z[rt<<1]+z[rt<<1|1];}//非常简洁的updata
void build(int l,int r,int rt)//建树
{
if (l==r) {z[rt].init(l,r);return;}//赋予线段树实际意义
int m=l+r>>1;
build(lson);//构建左子树
build(rson);//构建有子树
update(rt);//向上合并区间，
}
void modify(int l,int r,int rt,int nowl,int nowr,int v)//加法操作
{
//l,r,rt,表示当前所在的子树标号 rt, 所管理的区间为 l-r
// nowl, nowr, v 表示现在需要再 nowl-nowr 的区间内加上v
if (nowl<=l && r<=nowr) {color(rt,v);return;}//如果子树区间在所需区间内部，可进行加法标记操作
push(rt);//可有可无 求和的时候下传就可。
int m=l+r>>1;
if (nowl<=m) modify(lson,nowl,nowr,v);//在 l-m 区间内有所需区间，深入更新
if (nowr>m) modify(rson,nowl,nowr,v);// 在 m+1-r 区间存在所需区间，深入更新
update(rt);//注意这里是 m+1-r 是右区间，不是 m-r,这样规定的原因是防止 m 被 modify 两边
}
node query(int l,int r,int rt,int nowl,int nowr)//求和操作，返回结构体形，方便调用
{
if (nowl<=l && r<=nowr) return z[rt];//原理同 modify
push(rt);
int m=l+r>>1;
if (nowl<=m)
{
if (nowr>m) return query(lson,nowl,nowr)+query(rson,nowl,nowr);
return query(lson,nowl,nowr);
}
return query(rson,nowl,nowr);
}
int n,m;
signed main()//下面是常规操作
{
n=read(),m=read();
for (int i=1;i<=n;i++) a[i]=read();
build(root);
while (m--)
{
int opt,l,r,v;
opt=read();
if (opt==1)
{
l=read(),r=read(),v=read();
modify(root,l,r,v);
}
else
{
l=read(),r=read();
node q=query(root,l,r);
cout<<q.sum<<endl;
}
}
return 0;
}
线段树2
和线段树1不同的地方是存在一个乘法，可以简单的想到，多一个乘法标记不就完事了？但写完后发现，有加有乘，是有顺序的，不能简单的标记上，最后下穿。
现在出现第一个问题：如何实现乘法加法的顺序化
显然如果真的顺序化，那就成暴力了。
一种想法，在乘法的时候，现将加法标记下传，然后乘法标记。可是你发现 你调用的下传函数 push 中 就有你现在考虑的乘法标记函数 color2 ，这样就形成了环形调用，显然会报错。
之后我有想到加法标记的贡献问题，乘法的作用无非就两个，图书馆赶人啦，明天更