存档【线段树】-Toy模板网

这篇具有很好参考价值的文章主要介绍了存档【线段树】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

存一下写到一般的线段树

呃呃

1008-数据结构_2021秋季算法入门班第十一章习题：线段树、树状数组 (nowcoder.com)文章来源地址https://www.toymoban.com/news/detail-540201.html

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
const int mxn=1e5+10;
const int mxe=1e5+10;
const int mod=1e9+7;
const int Inf=1e18;

struct info{
    int sum;
};

info operator+(const info &l,const info &r){
    info res;
    res.sum=l.sum+r.sum;
    return res;
}

struct tag{
    int add,mul;
};

struct Segtree{
    info val;
    tag t;
}tree[mxe<<2][3];
//1为区间和,2为区间平方和

int N,M,op,l,r,x;
int a[mxn];

void pushup(int rt){
    tree[rt][1].val=tree[rt<<1][1].val+tree[rt<<1|1][1].val;
    tree[rt][2].val=tree[rt<<1][2].val+tree[rt<<1|1][2].val;
}
void settag1(int rt,int tot){

}
void settag2(int rt,int tot){

}
void pushdown(int rt,int tot){
    for(int i=1;i<=2;i++){
        if(tree[rt][i].t.add!=0||tree[rt][i].t.mul!=1){
            if(i==1){
                settag1(rt<<1,tot-tot/2);
                settag1(rt<<1|1,tot/2);
            }else{
                settag2(rt<<1,tot-tot/2);
                settag2(rt<<1|1,tot/2);
            }
            tree[rt][i].t.add=0;
            tree[rt][i].t.mul=1;
            return;
        }
    }
}
void build(int rt,int l,int r){
    if(l==r){
        //tag
        tree[rt][1].t.add=tree[rt][2].t.add=0;
        tree[rt][1].t.mul=tree[rt][2].t.mul=1;
        //val
        tree[rt][1].val.sum=a[l];
        tree[rt][2].val.sum=a[l]*a[l];
        return;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void modify(int rt,int l,int r,int x,int y,int k,int mode){
    if(x<=l&&r<=y){
        if(mode==1){
            //区间加
            settag1(rt,r-l+1);
            //1
            tree[rt][1].val.sum+=k*(r-l+1);
            //2
            tree[rt][2].val.sum=tree[rt][2].val.sum+2*k*tree[rt][1].val.sum+(r-l+1)*k*k;
        }else{
            //区间乘
            settag2(rt,r-l+1);
            //1
            tree[rt][1].val.sum*=k;
            //2
            tree[rt][2].val.sum*=k*k;
        }
        return;
    }
    pushdown(rt,r-l+1);
    int mid=l+r>>1;
    if(x<=mid) modify(rt<<1,l,mid,x,y,k,mode);
    if(y>mid) modify(rt<<1|1,mid+1,r,x,y,k,mode);
    pushup(rt);
}
info query(int rt,int l,int r,int x,int y,int mode){
    if(x<=l&&r<=y){
        if(mode==1){
            return tree[rt][1].val;
        }else{
            return tree[rt][2].val;
        }
    }
    pushdown(rt,r-l+1);
    int mid=l+r>>1;
    if(x>mid) return query(rt<<1|1,mid+1,y,x,y,mode);
    else if(y<=mid) return query(rt<<1,l,mid,x,y,mode);
    else{
        return query(rt<<1,l,mid,x,y,mode)+query(rt<<1|1,mid+1,r,x,y,mode);
    }
}
void solve(){
    cin>>N>>M;
    for(int i=1;i<=N;i++) cin>>a[i];
    build(1,1,N);
    while(M--){
        cin>>op;
        if(op==1){
            cin>>l>>r;
            cout<<query(1,1,N,l,r,1).sum<<'\n';
        }else if(op==2){
            cin>>l>>r;
            cout<<query(1,1,N,l,r,2).sum<<'\n';
        }else if(op==3){
            cin>>l>>r>>x;
            modify(1,1,N,l,r,x,2);
        }else{
            cin>>l>>r>>x;
            modify(1,1,N,l,r,x,1);
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;//cin>>__;
    while(__--)solve();return 0;
}

到了这里，关于存档【线段树】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！