线段树的区间修改

线段树2多加了个操作，pushdown就是用父节点的信息来下发到子节点进行更新，也即懒标记，用来区间修改

线段树的所有操作

pushup：子节点信息更新父节点信息

pushdown：父节点信息更新子节点信息

built：用堆的方式建立线段树

modify：修改一个值/一个区间的信息

query：询问一个区间的信息

pushup放在更新之后，pushdown放在更新之前

目录

1.一个简单的整数问题2

2.亚特兰蒂斯

3.维护序列

---

1.一个简单的整数问题2

243. 一个简单的整数问题2 - AcWing题库

 这题之前用树状数组也可以做，现在用线段树来做一下

#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
int w[N];
int n,m;
struct Node
{
    int l,r;
    ll sum,add;
}tr[4*N];
void pushup(int u)//用子节点信息更新父节点信息
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)//用父节点信息更新子节点信息
{
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(root.add)//假如有的加
    {
        left.add+=root.add,left.sum+=(ll)(left.r-left.l+1)*root.add;//左节点加上
        right.add+=root.add,right.sum+=(ll)(right.r-right.l+1)*root.add;//右节点加上
        root.add=0;//根节点重新赋值0
    }
}
void built(int u,int l,int r)//建立线段树
{
    if(l==r) tr[u]={l,r,w[l],0};//这个点的和等于w[l],add为0
    else
    {
        tr[u]={l,r,0,0};
        int mid=l+r>>1;
        built(u<<1,l,mid),built(u<<1|1,mid+1,r);//继续建左右子树
        pushup(u);//更新一下父节点信息
    }
}
void modify(int u,int l,int r,int d)//修改操作
{
    if(l<=tr[u].l&&r>=tr[u].r)//假如这个u区间已经在l~r里了，则直接修改
    {
        tr[u].sum+=(ll)(tr[u].r-tr[u].l+1)*d;//区间每个数都加上d
        tr[u].add+=d;//这个add+=d
    }
    else
    {
        pushdown(u);//先把父节点的信息更新到子节点中去，在修改
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,d);//假如这个值在左区间，则递归左区间进行查找这个值进行修改
        if(r>mid) modify(u<<1|1,l,r,d);//假如这个值在右区间，则递归右区间进行查找这个值进行修改
        pushup(u);//修改完后更新父节点信息
        
    }
}
ll query(int u,int l,int r)//询问操作
{
    if(tr[u].l>=l&&r>=tr[u].r) return tr[u].sum;//假如这个区间在l~r中了，则直接返回
    pushdown(u);//先把父节点的信息更新给子节点里
    ll ans=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) ans=query(u<<1,l,r);//假如在左区间
    if(r>mid) ans+=query(u<<1|1,l,r);//假如在右区间，则加上
    return ans;//返回结果
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    built(1,1,n);//建立线段树
    char op[2];
    while(m--)
    {
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(*op=='Q') printf("%lld\n",query(1,l,r));//询问则直接输出
        else
        {
            scanf("%d",&d);
            modify(1,l,r,d);//修改
        }
    }
    return 0;
}

2.亚特兰蒂斯

247. 亚特兰蒂斯 - AcWing题库

这题拓展性不大，自己斟酌着看 ，比赛难想

微分思想，把x进行正方形切分，然后y值进行线段树进行求长度，每个长方形的面积S=(xi-xi-1)*len，然后把所有的面积加起来则为总面积

假如一个矩形，我们让其左边为+1，右边为-1

 然后用线段树进行两个操作

1.将某个区间【l,r】+k

2.整个区间长度大于0的区间总长为多少？也即len

线段树要存的节点信息

cnt：当前区间整个被覆盖的个数

len：不考虑祖宗节点cnt的前提下，cnt>0的区间总长度

#include
using namespace std;
const int N=1e4+10;
int n;
struct Segment//用来存横坐标
{
    double x,y1,y2;
    int k;
    bool operator< (const Segment &t)const//横坐标按照从小到大排序
    {
        return x
    }
}seg[N*2];
struct Node//存y，也即线段树
{
    int l,r;
    int cnt;//记录当前区间有多少个
    double len;//当前区间y的长度
}tr[8*N];
vector<double> ys;//用来离散化，把y值离散化到1~2*n中
void pushup(int u)//用子节点信息更新父节点信息
{
    if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];//假如当前区间被覆盖了，则加上对应的y的长度
    else if(tr[u].l!=tr[u].r) tr[u].len=tr[u<<1].len+tr[u<<1|1].len;//假如没有覆盖并且不是根节点，则长度等于两个子节点的长度和
    else tr[u].len=0;//假如是根节点则没有长度
}
void built(int u,int l,int r)//建立线段树
{
    tr[u]={l,r,0,0};//刚开始没操作的长度与覆盖数都为0
    if(l!=r)
    {
        int mid=l+r>>1;
        built(u<<1,l,mid),built(u<<1|1,mid+1,r);//建立左右区间
        //pushup(u)这里不用也行，因为刚开始没有数的时候就是0
    }
}
void modify(int u,int l,int r,int k)//修改某个区间的值
{
    if(tr[u].l>=l&&tr[u].r<=r)//假如当前区间在l~r中
    {
        tr[u].cnt+=k;//则直接修改
        pushup(u);//把修改传到子节点中
    }
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,k);//假如在左边有，则递归左边
        if(r>mid) modify(u<<1|1,l,r,k);//假如在右边有，则递归右边
        pushup(u);
    }
}
int find(double y)//离散化，把y离散到坐标里
{
    return lower_bound(ys.begin(),ys.end(),y)-ys.begin();//用二分找出y的位置
}
int main()
{
    int T=1;
    while(scanf("%d",&n),n)
    {
        ys.clear();//清空上一层的状态
        double x1,x2,y1,y2;
        for(int i=1,j=0;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            seg[j++]={x1,y1,y2,1},seg[j++]={x2,y1,y2,-1};//左边则+1，右边则-1，加到存x中的结构体中去
            ys.push_back(y1),ys.push_back(y2);//把y也存进离散化里头
        }
        //将y去重
        sort(ys.begin(),ys.end());
        ys.erase(unique(ys.begin(),ys.end()),ys.end());
        built(1,0,ys.size()-2);//建立一颗线段树
        sort(seg,seg+2*n);//将x从小到大排序
        double res=0;
        for(int i=0;i<2*n;i++)
        {
            if(i) res+=tr[1].len*(seg[i].x-seg[i-1].x);//当i>0才能计算
            modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);//修改线段树y中的值
        }
        printf("Test case #%d\n",T++);
        printf("Total explored area: %.2lf\n\n",res);
    }
    return 0;
}

3.维护序列

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

第一题的进阶版

需要记录两个pushdown的值，也即add与mul

 

#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
int w[N];
int n,m,p;
struct Node//线段树
{
    int l,r;
    int sum,add,mul;
}tr[4*N];
void pushup(int u)//子节点更新父节点
{
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}
void eval(Node &t,int add,int mul)//用来更新某个节点的值
{
    t.sum=((ll)t.sum*mul+(ll)(t.r-t.l+1)*add)%p;//总和等于原来的和*mul+数的多少*add
    t.mul=(ll)t.mul*mul%p;//新的mul等于原来的mul*mul
    t.add=((ll)t.add*mul+add)%p;//新的add=原来的add*mul+add
}
void pushdown(int u)//用父节点信息更新子节点信息
{
   eval(tr[u<<1],tr[u].add,tr[u].mul);//更新左节点信息
   eval(tr[u<<1|1],tr[u].add,tr[u].mul);//更新右节点信息
   tr[u].add=0,tr[u].mul=1;//清空
}
void built(int u,int l,int r)//用来建立线段树
{
    if(l==r) tr[u]={l,r,w[l],0,1};
    else
    {
        tr[u]={l,r,0,0,1};
        int mid=l+r>>1;
        built(u<<1,l,mid),built(u<<1|1,mid+1,r);//建立左右子树
        pushup(u);//更新一遍父节点信息
    }
}
void modify(int u,int l,int r,int add,int mul)//修改操作
{
    if(tr[u].l>=l&&tr[u].r<=r) eval(tr[u],add,mul);//假如这个区间在l~r之间直接更新
    else
    {
        pushdown(u);//把之前的父节点信息更新到子节点信息中去
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,add,mul);//假如左边有这部分区间，则递归更新
        if(r>mid) modify(u<<1|1,l,r,add,mul);//假如右边有这部分区间，则递归更新
        pushup(u);//更新一遍父节点信息
    }
}
int query(int u,int l,int r)//询问操作
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;//假如这个区间在l~r之间则直接返回sum
    pushdown(u);//把父节点信息传递到子节点中去
    int mid=tr[u].l+tr[u].r>>1;
    int res=0;
    if(l<=mid) res=query(u<<1,l,r);//假如左边有这个区间
    if(r>mid) res=(res+query(u<<1|1,l,r))%p;//假如右边也有这个区间则加上
    return res;//返回答案
}
int main()
{
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    built(1,1,n);//建立线段树
    scanf("%d",&m);
    int op,l,r,d;
    while(m--)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)
        {
            scanf("%d",&d);
            modify(1,l,r,0,d);//乘d相当于加0乘d
        }
        else if(op==2)
        {
            scanf("%d",&d);
            modify(1,l,r,d,1);//加d相当于加d乘1
        }
        else printf("%d\n",query(1,l,r));//输出询问
    }
    return 0;
}