写这个类型博客的目的就是想总结一下某个专题的知识点，方便以后比赛前复习，由于太菜，如有错误，还请斧正。

很早就想写这个博客了，但实在是太菜了，以至于每次自己手搓线段树都会出bug（还是那种自己找不出的那种），再加上对线段树的理解也不够，刷的线段树的题也不多，所以就搁置下来了。这次开始写主要是因为牛客的线段树专场。。。

首先，我们什么时候要用到线段树呢？

1.插入点型

对于这种线段树，通常是向线段树中插入点，即对应一个叶子节点的信息，而线段树中所有节点也都是记录的关于以该点为根的子树中已插入的点的统计信息，询问通常是问线段树中某个区间对叶子节点的统计信息

2.线性覆盖型

对于这种线段树，与第三种有一下共同特点：所有询问和插入操作都是以区间为单位的，每次都是对一个区间进行操作。每个节点通常会用一个变量来记录以它为跟的子树的相关信息，在回溯过程中更新此变量。当操作的区间能完整的覆盖一个节点对应的区间时直接对该节点操作，不再向下操作。

简单来说就是点操作和区间操作（当然如果是复杂度比较低的题目可以直接暴力）

点操作算是线段树的入门，在这里就不一一赘述了，不会的同学可以看看下面这个博客

https://www.luogu.com.cn/blog/wsr/xian-duan-shu-dan-dian-xun-wen-xiu-gai-ru-men

接下来是区间上的操作，区间上的操作最重要的是lazy标记，因为如果每次修改都修改所有符合条件数组的话，花费的时间和暴力是没区别的，因此有了lazy标记（果然懒是一切发展的原动力），每次如果我们访问的范围在修改区间内就lazy标记一下（等需要下传lazy标记的时候再搞），如果访问范围包含修改范围则继续二分访问（忘了是不是叫这个名，但用到二分思想）。当然lazy标记可以标记很多种运算模式，但需要注意的一点是，当一道题目中出现多种运算方式时，就需要多个标记。

接下来是最重要的部分贴代码（这里贴的是包含加乘覆盖添加的代码，是最近的牛客线段树专场的代码，比赛时修了好几个小时也没改对QAQ）

题目链接：https://ac.nowcoder.com/acm/contest/5759/D

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
#define endl '\n'
const int MAXN = 1e6+10;
int n,m;
ll p,a[MAXN],atag[MAXN],mtag[MAXN],ctag[MAXN],tree[MAXN];//atag表示加标记 ctag表示覆盖标记 mtag表示乘标记 tree存和 a是一开始的数 
 
void Pushup(int rt){tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%p;}//更新 
 
void Pushdown(int rt,int ln,int rn){//下传 
    if(ctag[rt]!=-1){//先判断覆盖操作，如果有覆盖操作其他操作清零 
        ctag[rt<<1]=ctag[rt<<1|1]=ctag[rt];
        tree[rt<<1]=ctag[rt]*ln%p;
        tree[rt<<1|1]=ctag[rt]*rn%p;
        atag[rt<<1]=atag[rt<<1|1]=0;
        mtag[rt<<1]=mtag[rt<<1|1]=1;
        ctag[rt]=-1;
    }
    if(mtag[rt]!=1){ 
        mtag[rt<<1]=(mtag[rt<<1]*mtag[rt])%p;
        mtag[rt<<1|1]=(mtag[rt<<1|1]*mtag[rt])%p;
        atag[rt<<1]=(atag[rt<<1]*mtag[rt])%p;
        atag[rt<<1|1]=(atag[rt<<1|1]*mtag[rt])%p;
        tree[rt<<1]=(tree[rt<<1]*mtag[rt])%p;
        tree[rt<<1|1]=(tree[rt<<1|1]*mtag[rt])%p;
        mtag[rt]=1;
    }
    if(atag[rt]){
        atag[rt<<1]=(atag[rt<<1]+atag[rt])%p;
        atag[rt<<1|1]=(atag[rt<<1|1]+atag[rt])%p;
        tree[rt<<1]=(tree[rt<<1]+atag[rt]*ln)%p;
        tree[rt<<1|1]=(tree[rt<<1|1]+atag[rt]*rn)%p;
        atag[rt]=0;
    }
}
 
void Build(int l,int r,int rt){//建树 
    atag[rt]=0; ctag[rt]=-1; mtag[rt]=1;
    if(l==r){
        tree[rt]=a[l]%p;
        return ;
    }
    int mid=(l+r)/2;
    Build(ls);
    Build(rs);
    Pushup(rt);
}
 
void Add(int L,int R,int C,int l,int r,int rt){//加操作 
    if(L<=l&&R>=r){
        tree[rt]=(tree[rt]+1ll*C*(r-l+1))%p;
        atag[rt]=(atag[rt]+C)%p;
        return ;
    }
    int mid=(l+r)/2;
    Pushdown(rt,mid-l+1,r-mid);
    if(L<=mid)Add(L,R,C,ls);
    if(R>mid)Add(L,R,C,rs);
    Pushup(rt);
}
 
void Mul(int L,int R,int C,int l,int r,int rt){//乘操作 
    if(L<=l&&R>=r){
        tree[rt]=tree[rt]*C%p;
        atag[rt]=atag[rt]*C%p;
        mtag[rt]=mtag[rt]*C%p;
        return ;
    }
    int mid=(l+r)/2;
    Pushdown(rt,mid-l+1,r-mid);
    if(L<=mid)Mul(L,R,C,ls);
    if(R>mid)Mul(L,R,C,rs);
    Pushup(rt);
}
 
 
void Change(int L,int R,int C,int l,int r,int rt){//覆盖操作 
    if(L<=l&&R>=r){
        tree[rt]=1ll*(r-l+1)*C%p;
        ctag[rt]=C%p;
        atag[rt]=0;
        mtag[rt]=1;
        return ;
    }
    int mid=(l+r)/2;
    Pushdown(rt,mid-l+1,r-mid);
    if(L<=mid)Change(L,R,C,ls);
    if(R>mid)Change(L,R,C,rs);
    Pushup(rt);
}
 
ll Query(int L,int R,int l,int r,int rt){//求和操作 
    if(L<=l&&R>=r)return tree[rt]%p;
    int mid=(l+r)/2;
    Pushdown(rt,mid-l+1,r-mid);
    ll ans=0;
    if(L<=mid)ans=(ans+Query(L,R,ls))%p;
    if(R>mid)ans=(ans+Query(L,R,rs))%p;
    return ans;
}