蒟蒻刚学线段树，求调

miaoborui123456789 @ 2024-12-08 21:52:37

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1e6 + 7;
ll n , m;

ll num[N];
ll tree[4*N];
ll lazy[4*N];

void build(ll s , ll t , ll p){
    if(s == t){
        tree[p] = num[s];
        return ;
    }
    ll mid = s + ((t-s) >> 1);
    build(s , mid , p * 2) , build(mid + 1 , t , (p * 2) + 1);
    tree[p] = tree[p * 2] + tree[(p * 2) + 1];
}

void push_down(ll root, ll L, ll R) {
    if (lazy[root]) {
        lazy[root * 2] += lazy[root];
        lazy[root * 2 + 1] += lazy[root];
        ll mid = L + ((R-L)>>1);
        tree[root * 2] += lazy[root] * (mid - L + 1);
        tree[root * 2 + 1] += lazy[root] * (R - mid);
        lazy[root] = 0;
    }
}

ll get_sum(ll l , ll r , ll s , ll t , ll p){
    if(l <= s && t <= r){
        return tree[p];
    }

    ll mid = s + ((t-s) >> 1);
    push_down(p,l ,r);
    ll sum = 0;
    if(l <= mid){
        sum += get_sum(l , r , s , mid , p * 2);
    }
    if(r > mid){
        sum += get_sum(l , r , mid + 1 , t , p * 2 + 1);
    }
    return sum;
}

void update(ll l , ll r , ll s , ll t , ll c , ll p){
    if(l <= s && t <= r){
        tree[p] = (t-s + 1)*c;
        lazy[p] += c;
        return ;
    }

    ll mid = s + ((t-s) >> 1);
    push_down(p,l ,r);
    if(l <= mid){
        update(l , r , s , mid , c , p * 2);
    }
    if(r > mid){
        update(l , r , mid + 1 , t , c , p * 2 + 1);
    }
    return ;
}

int main(){
    cin>>n>>m;
    for(int i = 1 ; i <= n ; i++){
        cin>>num[i];
    }
    build(1,n,1);
//  for(int i = 1 ; i <= n ; i++){
//      cout<<tree[i]<<" ";
//  }
    while(m--){
        ll opt;
        cin>>opt;
        if(opt == 1){
            ll x , y , k;
            cin>>x>>y>>k;
            update(x,y,1,n,k,1);
//          update(x,y,1,n,k,1);
        }else{
            ll x , y;
            cin>>x>>y;
            cout<<get_sum(x,y,1,n,1);
            puts("");
        }
    }
    return 0;
}

by pies_0x @ 2024-12-08 21:54:39

@miaoborui123456789 看注释

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1e6 + 7;
ll n , m;

ll num[N];
ll tree[4*N];
ll lazy[4*N];

void build(ll s , ll t , ll p){
    if(s == t){
        tree[p] = num[s];
        return ;
    }
    ll mid = s + ((t-s) >> 1);
    build(s , mid , p * 2) , build(mid + 1 , t , (p * 2) + 1);
    tree[p] = tree[p * 2] + tree[(p * 2) + 1];
}

void push_down(ll root, ll L, ll R) {
    if (lazy[root]) {
        lazy[root * 2] += lazy[root];
        lazy[root * 2 + 1] += lazy[root];
        ll mid = L + ((R-L)>>1);
        tree[root * 2] += lazy[root] * (mid - L + 1);
        tree[root * 2 + 1] += lazy[root] * (R - mid);
        lazy[root] = 0;
    }
}

ll get_sum(ll l , ll r , ll s , ll t , ll p){
    if(l <= s && t <= r){
        return tree[p];
    }

    ll mid = s + ((t-s) >> 1);
    push_down(p,l ,r);
    ll sum = 0;
    if(l <= mid){
        sum += get_sum(l , r , s , mid , p * 2);
    }
    if(r > mid){
        sum += get_sum(l , r , mid + 1 , t , p * 2 + 1);
    }
    return sum;
}

void update(ll l , ll r , ll s , ll t , ll c , ll p){
    if(l <= s && t <= r){
        // tree[p] = (t-s + 1)*c; 你原来的
        tree[p] += (t-s + 1)*c;
        lazy[p] += c;
        return ;
    }

    ll mid = s + ((t-s) >> 1);
    push_down(p,l ,r);
    if(l <= mid){
        update(l , r , s , mid , c , p * 2);
    }
    if(r > mid){
        update(l , r , mid + 1 , t , c , p * 2 + 1);
    }
    return ;
}

int main(){
    cin>>n>>m;
    for(int i = 1 ; i <= n ; i++){
        cin>>num[i];
    }
    build(1,n,1);
//  for(int i = 1 ; i <= n ; i++){
//      cout<<tree[i]<<" ";
//  }
    while(m--){
        ll opt;
        cin>>opt;
        if(opt == 1){
            ll x , y , k;
            cin>>x>>y>>k;
            update(x,y,1,n,k,1);
//          update(x,y,1,n,k,1);
        }else{
            ll x , y;
            cin>>x>>y;
            cout<<get_sum(x,y,1,n,1);
            puts("");
        }
    }
    return 0;
}

by hepp @ 2024-12-08 21:54:42

push_down(p,l ,r);

应为

push_down(p,s ,t);

@miaoborui123456789

by pies_0x @ 2024-12-08 21:57:17

@miaoborui123456789 哦，对，楼上提醒我了，你仔细改改你的 updata 函数吧，注意 l, r 和 s, t 的区别

by miaoborui123456789 @ 2024-12-08 22:00:07

OK，谢谢各位大牛