准确说是为了以后好复习哈哈


线段树可以实现动态更新区间最大值最小值,区间和(计数)的操作。
当然具体考试的时候需要将pushuppushdown之类的改一改。

区间加和区间减类型

    /*
    notonlybutsuccess的线段树
    包含区间加区间减查询 
    */
    #include<bits/stdc++.h>
    #define For(i,l,r) for(int i = l;i<=r;i++)
    #define N 100000
    #define LL long long
    using namespace std;
    LL lt[N<<2];//line tree
    LL laz[N<<2];//懒标记,表示他的子节点需要更新 
    int pushup(int u)return lt[u]=lt[u<<1]+lt[u<<1|1];//根据子节点更新本节点 
    void build(int l,int r,int u){//建立线段树,不断输入,不断更新 
        if(l==r){cin>>lt[u];return;}//如果为叶子节点那么输入数据 
        int mid = l+r>>1;//不然分线段 
        build(l,mid,u>>1);//建立左线段 
        build(mid+1,r,u>>1|1);//建立右线段 
        pushup(u);//根据所有线段更新本届点 
    }
    void pushdown(int rt,int len){//懒标记传递 
        if(laz[rt]){//如果存在懒标记 
            laz[rt<<1]+=laz[rt];//给左子节点的懒标记增加 
            laz[rt<<1|1]+=laz[rt];//给右子节点的懒标记增加 
            lt[rt<<1]+=laz[rt]*(len-(len>>1));//更新左线段的值 
            lt[rt<<1|1]+=laz[rt]*(len>>1);//更新右线段的值 
            laz[rt]=0;//清空懒标记 
        }
    }
    void upload(int L,int R,int c,int l,int r,int u){//修改 
        if(l>=L&&r<=R){//如果在区间内,直接进行操作 
            laz[u]+=c;
            lt[u]+=c*(r-l+1);
            return;
        }
        pushdown(u,r-l+1);//不然清空懒标记 
        int mid = l+r>>1; 
        if(L<=mid)upload(L,R,c,l,mid,u<<1);//如果左线段在范围内,更新左线段 
        if(mid+1<=R)upload(L,R,c,mid+1,u<<1|1);//如果右线段在范围内,更新右线段 
        pushup(u);//根据左右更新本节点 
    }
    LL query(int L,int R,int l,int r,int u){//查询区间和 
        if(L<=l&&r<=R){//如果已经是叶子节点,返回叶子节点的值 
            return lr[u];
        }
        pushdown(u,r-l+1);//清空懒标记 
        ll ans  = 0; 
        int mid=l+r>>1;
        if(L<=mid)ans+=query(L,R,l,mid,u<<1);//如果左线段右子有在查询线段内的更新答案 
        if(mid+1<=R)ans+=query(L,R,mid+1,r,u<<1|1);//如果右线段有在查询线段内的更新答案 
        return ans;
    }
    int main(){
        int n,m;
        cin>>n>>m;
        buils(1,n,1);
        For(i,1,m){
            int ope;
            cin>>ope;
            if(ope){
                int l,r;
                ll c;
                cin>>l>>r>>c;
                upload(l,r,c,1,n,1);//在整个线段修改 
            }
            else{
                int l,r;
                cin>>l>>r;
                cout<<query(l,r,1,n,1);//在整个线段查询 
            }
        }
    }
     
name.com购买域名廉价稳定无需备案 年付.xyz.site.life$3点击购买赠送5$优惠券
racknerd购买无需备案CN2服务器,速度高速稳定节日优惠力度强 节日会推出各种优惠套餐【点击注册】目前推出3H2.5G40GB6T每年$27.80两年$55.60套餐【快来注册
Last modification:May 26th, 2020 at 10:48 pm
觉得好的话就评论,转发,投币。