线段树真是个有趣的东东，那个 \(lazytag\) 把我看得一头汗。
感觉线段树这个东西呢理解了 \(lazytag\) 多打几遍就是闭眼打的，但是理解不了的话咳咳，那就完蛋了。
Part 1 线段树是个啥
线段树是个有趣的树，这棵树呢每个节点表示一个区间。在这个神奇的书中根节点表示整个区间 \([1,n]\)，他的左右儿子为 \([1,mid]\) 和 \([mid+1,n]\)，以此类推。
长成这样：图真是丑炸了
相信根据图大家一定能理解线段树 qwq
下面的我就以 This problem 做例题讲线段树啦。
Part 2 线段树的建树和基础
首先我们要了解一些很简单的建树操作。
我们都知道，线段树可以用一个非常简洁优美的方式存储，左儿子为 \(v\times 2\)，右儿子为 \(v\times 2+1\)，他们的父亲为向下取整的 \(s\div 2\)。
然后呢我们就可以写两个函数：
int ls(int x){return x<<1; }
int rs(int x){return x<<1|1;}
这个位运算不要管他，装逼用的（滑稽
然后是建树。
建树真心没什么好说的，参数三个，\(l\)，\(r\)，\(now\)，\(l\) 和 \(r\) 表示在 \([l,r]\) 的区间建树， \(now\) 表示当前的节点编号。
每次我们选择 \(mid\)，也就是向下取整的 \((l+r)\div 2\) 为左儿子的右端点，\(mid+1\) 为右儿子的左端点，然后我们递归挨个建树就可以廖。
最后回溯时我们应该更新当前点，所以我们要有个叫 push_up 的东西，这个东东长的很简单，就这样：
void push_up(int now)
{
f[now]=f[ls(now)]+f[rs(now)];
}
下面是建树的代码，其中的 \(lazy\) 请忽略，下个部分详细讲讲这个东西的作用。
void build(int l,int r,int now)
{
lazy[now]=0;
int mid=(l+r)>>1;//中点
if(l==r)//如果是叶子节点的话
{
f[now]=a[l];//直接复制完事
return ;
}
build(l,mid ,ls(now));//递归建立左子树
build(mid+1,r,rs(now));//递归建立右子树
push_up(now);//更新
}
注意：\(f\) 数组一定要开四倍空间
Part 2 区间修改
线段树的查询为 \(O(log_2 n)\) 的（常数还大），如果这个东西无法修改，完全可以用码量少的 ST 表。
这两东西空间还不小对吧。
线段树的区间修改是整个过程的核心，核心为上文的 \(lazy\)，这个东西全名 \(lazytag\)，是个神奇的东西。
我们都知道，如果我们每次暴力给区间 \([l,r]\) 加上一个值，很显然这个速度会慢到飞起，肯定不是 \(\log\) 的，这时候有个叫 \(lazy\) 的东西横空出世，拯救了快没的线段树（误
首先，线段树是个很懒的数据结构，能不干啥就不干啥（开始诋毁线段树 ing
如果我们要给 \([l,r]\) 加上 \(v\)，我们该怎么办呢？
直接标记一下这个区间要加多少不就得了？
什么？这么简单？
不错，就这么简单。
\(lazy\) 就是标记这个区间的。
我们每次枚举区间，如果这个区间包含在要更新的区间之内，我们就为这个区间打上标记，否则递归。
别忘了回溯要 push_up 进行更新呀！
下面是代码实现了。
首先我们要有个压入标记的函数，叫 push_tag。
这个函数十分简单，只不过是一两行的事情。
void push_tag(int now,int l,int r,int val)
{
f[now]+=(r-l+1)*val;
lazy[now]+=val;
}
下面我们发现在每次更新的时候我们应该下放一下标记给这个家伙的儿子们，因为如果不是 \([l,r]\) 以内的区间的话，打上 \(lazy\) 是没卵用的。
所以我们要写一个简单的函数叫 push_down
这个函数也很简单，只不过是对这个区间的左右儿子放标记而已，仅此而已。
void push_down(int now,int l,int r)
{
if(lazy[now])
{
int mid=(l+r)>>1;
push_tag(ls(now),l,mid ,lazy[now]);//左儿子
push_tag(rs(now),mid+1,r,lazy[now]);//右儿子
lazy[now]=0;
}
}
最终就是区间修改。经过上面的讲解，写起来也应该很容易，代码：
void updata(int l,int r,int s,int t,int now,int val)
{
if(l<=s&&r>=t)//在区间内
{
push_tag(now,s,t,val);//直接打标机
return ;
}
int mid=(s+t)>>1;
push_down(now,s,t);//下放标记
if(l<=mid)updata(l,r,s,mid ,ls(now),val);//递归左儿子
if(r> mid)updata(l,r,mid+1,t,rs(now),val);//递归右儿子
push_up(now);//更新
}
Part 3 区间查询
这个其实也很简单，代码和区间修改很相似。
如果遇到了包括在内的区间，直接返回，否则我们就递归。
思路也很简单，代码和上面很相似，细节见代码吧，如下：
int ask(int l,int r,int s,int t,int now)
{
if(l<=s&&r>=t)return f[now];
int mid=(s+t)>>1;
push_down(now,s,t);
int sum=0;
if(l<=mid)sum+=ask(l,r,s,mid ,ls(now));
if(r> mid)sum+=ask(l,r,mid+1,t,rs(now));
return sum;
}
最后，完全代码：
#include<iostream>
#define int long long
#define MAXN 100000
using namespace std;
int f[MAXN*4+10],lazy[MAXN*4+10],a[MAXN+10];
int ls(int now){return now<<1; }
int rs(int now){return now<<1|1;}
void push_tag(int now,int l,int r,int val)
{
f[now]+=(r-l+1)*val;
lazy[now]+=val;
}
void push_up(int now)
{
f[now]=f[ls(now)]+f[rs(now)];
}
void push_down(int now,int l,int r)
{
if(lazy[now])
{
int mid=(l+r)>>1;
push_tag(ls(now),l,mid ,lazy[now]);
push_tag(rs(now),mid+1,r,lazy[now]);
lazy[now]=0;
}
}
void build(int l,int r,int now)
{
lazy[now]=0;
int mid=(l+r)>>1;
if(l==r)
{
f[now]=a[l];
return ;
}
build(l,mid ,ls(now));
build(mid+1,r,rs(now));
push_up(now);
}
int ask(int l,int r,int s,int t,int now)
{
if(l<=s&&r>=t)return f[now];
int mid=(s+t)>>1;
push_down(now,s,t);
int sum=0;
if(l<=mid)sum+=ask(l,r,s,mid ,ls(now));
if(r> mid)sum+=ask(l,r,mid+1,t,rs(now));
return sum;
}
void updata(int l,int r,int s,int t,int now,int val)
{
if(l<=s&&r>=t)
{
push_tag(now,s,t,val);
return ;
}
int mid=(s+t)>>1;
push_down(now,s,t);
if(l<=mid)updata(l,r,s,mid ,ls(now),val);
if(r> mid)updata(l,r,mid+1,t,rs(now),val);
push_up(now);
}
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int p=1;p<=n;p++)
cin>>a[p];
build(1,n,1);
for(int p=1;p<=m;p++)
{
int opt,l,r,val;
cin>>opt>>l>>r;
if(opt==1)cin>>val,updata(l,r,1,n,1,val);
else cout<<ask(l,r,1,n,1)<<endl;
}
}