题解：P3372 【模板】线段树 1 || 普通递归线段树详解
什么是线段树
相信很多同学早就有听过这个名字，会觉得这个数据结构很难、很复杂。不是的。线段树的原理其实很简单。顾名思义，线段树是一种二叉树，由线段构成。每一个节点都有一个自己管理的区间，然后将这个区间平分成两部分后，左孩子管理左半区间，右孩子管理右半区间。
举个例子，现在有一个长度为
细心的同学发现线段树的叶子节点只管理一个点。没错，一直细分下去就会只剩下一个点了。
线段树上的每一个节点都可以存储下来这段区间的一些信息，比如区间和。
线段树的作用
我们现在回到这道模版题。这道题目可以用很简单的
最简单的线段树可以解决单点修改、区间查询，区间修改、单点查询以及区间修改、区间查询。这道题目属于区间修改、区间查询。
线段树的实现过程
查询操作
现在假如我们要在前面那棵线段树上查询
当遇到完全被要查询的区间包含的节点，我们就停止向下的递归，并返回该节点的信息。
在回溯的时候，我们将两个子节点的信息合并并返回即可。
发现遍历的节点数基本为树高，二线段树的高度为
修改操作
我们可以尝试类比查询的做法。但是我们会发现一个问题：如果遇到完全被修改区间包含的节点，直接停止会出事，下面的节点信息也应当要修改。
但是如果继续递归下去时间复杂度就会退化到
顾名思义，他很懒。这个标记懒得动。这个标记的含义是以它为根的子树需要修改的信息。当我们有需要用到下面的节点时，我们将懒标记下传，即将修改信息传给儿子，这样就不用每次修改都递归到最底层了。
时间复杂度同修改，
线段树的代码实现
接下来将详细谈谈线段树该如何写。
首先得搞清楚每个节点的序号。对于一个二叉树，有一个很简单的标序号方法：对于节点
使用位运算优化时间，这里就可以写作： :::info[左孩子右孩子]
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;}
:::
接下来就是递归回溯时合并的操作了，对于这道题目，合并的是子节点的和。
:::info[push_up 操作]
```cpp line-numbers
inline void push_up(int now){sum[now]=sum[lc(now)]+sum[rc(now)];}
:::
然后是修改时修改某个节点的操作。这里传的参数要有区间左右端点（用于计算区间长度，因为这道题目是区间加和）、以及加多少。
记得修改懒标记。
:::info[修改单个线段树节点]
```cpp line-numbers
inline void f(int now,int l,int r,int k){sum[now]+=(r-l+1)*k,tag[now]+=k;}
:::
前面提到懒标记在遍历到要用的点的时候要提前下传给孩子，具体操作其实就是前面的那个修改单个节点的操作，把左右孩子都修改懒标记存的内容，然后将懒标记清零。
:::info[push_down 操作]
```cpp line-numbers
inline void push_down(int now,int l,int r){
int mid=l+r>>1;
f(lc(now),l,mid,tag[now]);
f(rc(now),mid+1,r,tag[now]);
tag[now]=0;
}
:::
这道题目初始有一个序列，因此我们要给线段树初始化。具体操作是递归下去后到叶子节点直接更新值，然后回溯的时候合并即可。
:::info[build 操作]
```cpp line-numbers
inline void build(int now,int l,int r){
if(l==r){
sum[now]=a[l];
return;
}
int mid=l+r>>1;
build(lc(now),l,mid);
build(rc(now),mid+1,r);
push_up(now);
}
:::
查询操作和上面说的一样。只走有交集的节点，到完全包含的节点停止递归，并修改值与懒标记。
在往下递归的时候，记得边递归边下传懒标记。
在回溯的时候，记得合并更新状态。
:::info[update 操作]
```cpp line-numbers
inline void update(int nl,int nr,int l,int r,int now,int k){
if(l>nr||r<nl) return;
if(l>=nl&&r<=nr){
f(now,l,r,k);
return;
}
push_down(now,l,r);
int mid=l+r>>1;
update(nl,nr,l,mid,lc(now),k);
update(nl,nr,mid+1,r,rc(now),k);
push_up(now);
}
:::
最后是查询操作了。每一次返回的是左右两个孩子的结果的加和。如果跑到区间外了，为了不影响结果，返回 $0$。
记得下传懒标记。
:::info[query 操作]
```cpp line-numbers
inline int query(int now,int l,int r,int ql,int qr){
if(l>qr||r<ql) return 0;
if(l>=ql&&r<=qr) return sum[now];
push_down(now,l,r);
int res=0,mid=l+r>>1;
res+=query(lc(now),l,mid,ql,qr);
res+=query(rc(now),mid+1,r,ql,qr);
return res;
}
:::
然后就结束了。。
:::info[完整代码]
```cpp line-numbers
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,opt,x,y,k,a[100005],sum[400005],tag[400005];
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;}
inline void f(int now,int l,int r,int k){sum[now]+=(r-l+1)*k,tag[now]+=k;}
inline void push_up(int now){sum[now]=sum[lc(now)]+sum[rc(now)];}
inline void push_down(int now,int l,int r){
int mid=l+r>>1;
f(lc(now),l,mid,tag[now]);
f(rc(now),mid+1,r,tag[now]);
tag[now]=0;
}
inline void build(int now,int l,int r){
if(l==r){
sum[now]=a[l];
return;
}
int mid=l+r>>1;
build(lc(now),l,mid);
build(rc(now),mid+1,r);
push_up(now);
}
inline void update(int nl,int nr,int l,int r,int now,int k){
if(l>nr||r<nl) return;
if(l>=nl&&r<=nr){
f(now,l,r,k);
return;
}
push_down(now,l,r);
int mid=l+r>>1;
update(nl,nr,l,mid,lc(now),k);
update(nl,nr,mid+1,r,rc(now),k);
push_up(now);
}
inline int query(int now,int l,int r,int ql,int qr){
if(l>qr||r<ql) return 0;
if(l>=ql&&r<=qr) return sum[now];
push_down(now,l,r);
int res=0,mid=l+r>>1;
res+=query(lc(now),l,mid,ql,qr);
res+=query(rc(now),mid+1,r,ql,qr);
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i = 1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--){
cin>>opt>>x>>y;
if(opt==1) cin>>k,update(x,y,1,n,1,k);
else cout<<query(1,1,n,x,y)<<'\n';
}
return 0;
}
:::
~~给个赞再走吧。。~~