线段树70分求调

ESxyz @ 2024-10-19 11:02:07

#include<bits/stdc++.h>
using namespace std;
#define N 114514
#define int long long

long long a[N];
struct nod{
    int l,r;
    int value;
    int add;
}tree[5*N];

void build(int l,int r,int i){
    tree[i]={l,r,0,0};
    //cout<<l<<" "<<r<<endl;
    if(l==r){
        tree[i].value=a[l];
        return;
    }
    int mid=l+(r-l)/2;
    build(l,mid,i*2);
    build(mid+1,r,i*2+1);
    tree[i].value=tree[i*2].value+tree[i*2+1].value;
}

void spr(int i){
    tree[i*2].value+=tree[i].add*(tree[i*2].r-tree[i*2].l+1);
    tree[i*2+1].value+=tree[i].add*(tree[i*2+1].r-tree[i*2+1].l+1);
    tree[i*2].add+=tree[i].add;
    tree[i*2+1].add+=tree[i].add;
    tree[i].add=0;
}

long long getsum(int l,int r,int i){
    if(tree[i].r<l||tree[i].l>r)return 0;
    if(tree[i].l>=l&&tree[i].r<=r)return tree[i].value;
    spr(i);
    return getsum(l,r,i*2)+getsum(l,r,i*2+1);
}

void add(int l,int r,int i,int data){
    if(tree[i].r<l||tree[i].l>r)return;
    if(tree[i].l>=l&&tree[i].r<=r){
        tree[i].value+=data*(tree[i].r-tree[i].l+1);
        tree[i].add+=data;
        return;
    }
    tree[i].value+=data*(min(tree[i].r,r)-max(tree[i].l,l)+1);
    spr(i);
    add(l,r,i*2,data);
    add(l,r,i*2+1,data);
}

signed main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    build(1,n,1);
    while(m--){
        //for(int i=1;i<=4*n+5;i++)cout<<tree[i].l<<" "<<tree[i].r<<":"<<tree[i].value<<" "<<tree[i].add<<endl;cout<<endl;
        int q;
        scanf("%d",&q);
        int x,y;
        scanf("%d%d",&x,&y);
        if(q==1){
            int k;
            scanf("%d",&k);
            add(x,y,1,k);
        }
        else printf("%d\n",getsum(x,y,1));
    }
}

by Allmypeople @ 2024-10-19 11:04:39

@ESxyz

试试我的

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
int n,m;
ll a[N],w[N*4],t[N*4];
void pushup(const int u){
    w[u]=w[u*2]+w[u*2+1];
}
void build(const int u,int l,int r){
    if(l==r){
        w[u]=a[l];
        return;
    }
    int m=(l+r)/2;
    build(u*2,l,m);
    build(u*2+1,m+1,r);
    pushup(u);
}//建线段树 

bool in(int L,int R,int l,int r){
    return (l<=L)&&(R<=r);
}
bool out(int L,int R,int l,int r){
    return (L>r)||(R<l);
}
void make(int u,int len,ll x){
    t[u]+=x;
    w[u]+=len*x;
} 
void pushdown(int u,int l,int r){
    int m=(l+r)/2;
    make(u*2,m-l+1,t[u]);
    make(u*2+1,r-m,t[u]);
    t[u]=0;
}
void update(int u,int L,int R,int l,int r,ll x){
    if(in(L,R,l,r)) make(u,R-L+1,x);
    else if(!out(L,R,l,r)){
        int m=(L+R)/2;
        pushdown(u,L,R);
        update(u*2,L,m,l,r,x);
        update(u*2+1,m+1,R,l,r,x);
        pushup(u);
    }
}//区间修改 

ll query(int u,int L,int R,int l,int r){
    if(in(L,R,l,r)) return w[u];
    else if(!out(L,R,l,r)){
        int m=(L+R)/2;
        pushdown(u,L,R);
        return query(u*2,L,m,l,r)+query(u*2+1,m+1,R,l,r);
    }
    else return 0;
}//区间求和 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op>>x>>y;
        if(op==1){
            cin>>k;
            update(1,1,n,x,y,k);
        }
        else cout<<query(1,1,n,x,y)<<endl;
    }
    return 0;
}

by Manki233 @ 2024-10-19 11:13:01

@ESxyz 递归两遍？单词操作会退化到 O(nlogn)

by ESxyz @ 2024-10-19 11:33:35

@Allmypeople 纯数组有点难懂欸，但还是谢谢大佬

by ESxyz @ 2024-10-19 11:35:29

@Manki233 额这样吗？但是我是后三个点wa欸

by Manki233 @ 2024-10-19 11:48:34

@ESxyz 那就是你写错了，你看你 add 后面都没有 pushup