题解：P3373 【模板】线段树 2
Eterna
·
·
题解
算法介绍
线段树是一种基于分治的递归数据结构，可以快速处理许多区间问题，可以说是最重要的数据结构。
线段树所维护的询问需要满足区间可合并性，区间修改则需要考虑全局修改对询问结果的影响。
询问如：
\sum _{i=l}^{r} a_i=\sum _{i=l}^{mid} a_i +\sum _{i=mid+1}^{r} a_i,
\max _{i=l}^{r} a_i=\max(\max _{i=l}^{mid} a_i ,\max _{i=mid+1}^{r} a_i).
修改维护可行性与询问相关，所以不做枚举。
算法讲解
例题 1
已知一个数列，每次询问某个区间的最小值。
如果暴力的话显然是 O(nm)，无法接受。
但是如果可以提前知道一些区间的最小值，在把询问区间拆成已知的区间在合并答案就可以快速的处理询问了。
线段树就是这样处理的，而线段树的结构（n=6）如下图：
其中用 [l,r] 表示区间，下文同。
用 f(l,r) 表示区间 [l,r] 的最小值，如果我们要求 f(1,4)，则有 f(1,4)=\min(f(1,3),f(4,4))，而
又如 $f(2,5)=\min(f(2,3),f(4,4),f(5,5))$，$f(1,6)=f(1,6)$。
但是如何快速储存并查询这样的结构呢？
>如上图，我们发现线段树有一些空结点，使得线段树始终是满二叉树，所以我们采用满二叉树的命名方法。结点 $x$ 的左孩子是 $2x$，右孩子是 $2x+1$。
又如何快速找到这样的区间呢？
>首先，我们要知道线段树结点代表区间的规律。设某一结点代表了 $[l,r]$，又定义区间中点为 $\displaystyle mid=\lfloor \frac{l+r}{2} \rfloor$，则左孩子代表区间 $[l,mid]$，右孩子代表区间 $[mid+1,r]$。
>
>设询问区间为 $[l,r]$，如果我们到了一个代表 $[l',r']$ 的结点。
>有 $3$ 种情况：
>>1. 两个区间没有相交，表示为 $r'< l$ 或 $l'> r$。
>>2. 当前节点被询问区间完全包含，表示为 $l \le l' \le r' \le r$。
>>3. 其他情况，不满足上述条件即可。
>
>线段树一般采用递归的写法，从根结点向叶子结点
>
>第 $1$ 种不是合法的情况，返回一个极大值即可。
>
>第 $2$ 种代表找到了一个这样的区间，直接返回当前结点的区间所代表的最小值。
>
>第 $3$ 种代表有相交，但不包含，说明当前结点为根构成的子树上有满足条件的结点，暴力向两个孩子递归。
实现如下：
```cpp
int ask(int id,int l,int r,int x,int y)//id为结点编号，[l,r]为当前区间，[x,y]为询问区间
{
if(y<l||x>r)return 1e9;//第一种情况
if(x<=l&&y>=r)return t[id];//第二种情况
int mid=(l+r)/2,ans=1e9;//第三种情况
ans=min(ans,ask(id*2,l,mid,x,y));
ans=min(ans,ask(id*2+1,mid+1,r,x,y));
return ans;
}
```
仔细想想你又会发现不太对劲，我们的线段树还没有值啊。
首先，对于所有的叶子结点 $[l,r]$，显然有 $l=r$，所以可以直接将其赋值为 $a_l$。非叶子结点也好办，如果两个孩子区间已经初始化完成，那么直接取两个子区间的最小值的最小值就可以了。
所以从下自上的初始化就可以做到 $O(n)$ 了，那么这题也就做完了。
---
[例题 $2$](https://www.luogu.com.cn/problem/P3374)
> 已知一个数列，每次操作将某个数加上 $x$，或求出某区间每一个数的和。
>
> $1 \le n,m \le 5 \times {10}^5$。
区间求和与上面求 $\max$ 相同，但是我们发现他要求我们维护的序列是带修的。
对建树进行类比，直接递归到叶子结点暴力修改，然后从叶子结点一步步向上传递。
因为线段树大致是一颗满二叉树，层数是 $\log n$，所以如此修改是 $O(\log n)$。
[例题 $3$](https://www.luogu.com.cn/problem/P3372)
> 已知一个数列，每次操作将某区间每一个数加上 $x$，或求出某区间每一个数的和。
>
> $1 \le n,m \le {10}^5$。
区间求和大家肯定已经会了。
区间加呢？有一个直观的想法，我们可以暴力递归到区间 $[l,r]$ 的叶子结点，然后暴力修改。复杂度显然 $O(n)$。
参考代码：
```cpp
void add(int id,int l,int r,int x,int y,int v)
{
if(l==r)
{
sumv[id]+=v;
return;
}
int mid=l+r>>1;
if(x<=mid)add(id<<1,l,mid,x,y,v);
if(y>mid)add(id<<1|1,mid+1,r,x,y,v);
pushup(id);
}
```
我们发现，递归过程中，有时会满足一种情况，就是当前节点的整个子树都被加了。根据一般的线段树的性质，可以看出，只有当当前递归区间 $[l',r']$ 是询问区间 $[l,r]$ 的子区间时，才会出现这种情况。反之同理，出现这种情况，必然是当前区间是询问区间的子区间。
对于子区间的判别显然有 $l \le l' \le r' \le r$。
引入一个 `lazy` 的概念，如果当前区间是这样的区间，我们对 `lazy+=x`，用来代表当前区间整体被加上了 $x$，而它对答案的影响是加上了 $(r'+l'+1)x$。这其实是对一个区间的全局操作，所以我在前面说区间修改则需要考虑全局修改对询问结果的影响。
但是再次对以此法修改过的区间的子区间再次操作时，会导致计算错误。我们需要对 `lazy` 进行一个下传，对当前节点的两个孩子区间全局加上 `lazy`，然后归零当前节点的 `lazy`。
当对一个区间操作时，它会将目标区间拆成若干个区间，分别全局操作。所以操作复杂度是 $O(\log n)$。
故总复杂度可以做到 $O(m \log n)$。
---
[例题 $4$](https://www.luogu.com.cn/problem/P3373)
> 已知一个数列，每次操作将某区间每一个数加上 $x$，或将某区间每一个数乘上 $x$，或求出某区间每一个数的和。
>
> $1 \le n,q \le {10}^5$。
对于区间乘法，对加法简单类比就可以做到。但是既有加法，又有乘法不太好做。
若当前节点的乘法 `lazy` 值是 $x$，加法 `lazy` 值是 $y$，则记当前节点的 `lazy` 为二元组 $(x,y)$。代表使区间内每个数 $a_i \gets a_i x + y$。
若当前区间乘上了 $z$，则标记变为 $(a_i x + y)z = a_i x z + yz$，转换为二元组就是 $(xz,yz)$。也就是，乘法需要对乘法 `lazy` 和加法 `lazy` 同时乘上 $z$。
若当前区间加上了 $z$，则标记变为 $a_i x + y + z = a_i x + (y + z)$，转换为二元组就是 $(x,y+z)$。也就是，加法只需要对加法 `lazy` 加上 $z$。
按我们标记的定义，我们的标记下传应该先乘再加。
---
### 正确性证明
我们修改与查询时线段树选取的区间一定是操作区间的子区间。不难发现，只有选了两个节点在同一条从叶子节点到根的路径才会选择重复，而我们选择区间后就返回了，所以不可能选择区间不可能有交。线段树将区间划分到 $1$，不可能有选择不充分的情况。
所以，线段树可以不重复的选择最少区间表示已知区间。
### 代码实现
关于本题，其实就是[例题 $4$](https://www.luogu.com.cn/problem/P3373)。
最大问题就是取模不到位导致溢出，写代码的时候一定要多取模呀！
```cpp
#include<bits/stdc++.h>
#define N 100005
#define int long long
#define rd read()
#define gc getchar()
using namespace std;
int m,n,mod;
inline int read()
{
register int x=0,ss=1,s=gc;
while(!isdigit(s)&&s!='-')s=gc;
if(s=='-')ss=-1,s=gc;
while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
return ss*x;
}
int lazy[N<<2],lazy2[N<<2],sumv[N<<2];
inline void pushup(int id){sumv[id]=(sumv[id<<1]+sumv[id<<1|1])%mod;}
inline void build(int id,int l,int r)
{
lazy2[id]=1;
if(l==r)return sumv[id]=rd,void();
int mid=l+r>>1;
build(id<<1,l,mid),build(id<<1|1,mid+1,r),pushup(id);
}
inline void push(int id,int L,int v){(lazy[id]+=v)%=mod,(sumv[id]+=L*v)%=mod;}
inline void push2(int id,int v){(lazy[id]*=v)%=mod,(lazy2[id]*=v)%=mod,(sumv[id]*=v)%=mod;}
inline void pushdown(int id,int l,int r)
{
int mid=l+r>>1;
if(lazy2[id]!=1)push2(id<<1,lazy2[id]),push2(id<<1|1,lazy2[id]),lazy2[id]=1;
if(lazy[id])push(id<<1,mid-l+1,lazy[id]),push(id<<1|1,r-mid,lazy[id]),lazy[id]=0;
}
inline void update(int id,int l,int r,int x,int y,int v)
{
if(l>=x&&r<=y)return push2(id,v);
pushdown(id,l,r);int mid=l+r>>1;
if(x<=mid)update(id<<1,l,mid,x,y,v);
if(y>mid)update(id<<1|1,mid+1,r,x,y,v);
pushup(id);
}
inline void insert(int id,int l,int r,int x,int y,int v)
{
if(l>=x&&r<=y)return push(id,r-l+1,v);
pushdown(id,l,r);int mid=l+r>>1;
if(x<=mid)insert(id<<1,l,mid,x,y,v);
if(y>mid)insert(id<<1|1,mid+1,r,x,y,v);
pushup(id);
}
inline int ask(int id,int l,int r,int x,int y)
{
if(l>=x&&r<=y)return sumv[id];
pushdown(id,l,r);int ans=0,mid=l+r>>1;
if(x<=mid)ans+=ask(id<<1,l,mid,x,y);
if(y>mid)ans+=ask(id<<1|1,mid+1,r,x,y);
return ans%mod;
}
signed main()
{
n=rd,m=rd,mod=rd,build(1,1,n);
for(int i=1,x,l,r;i<=m;i++)
{
x=rd,l=rd,r=rd;
if(x==1)update(1,1,n,l,r,rd);
if(x==2)insert(1,1,n,l,r,rd);
if(x==3)cout<<ask(1,1,n,l,r)<<'\n';
}
return 0;
}
```