(模板)线段树(单点更新,区间更新)模板

痛定思痛。 2022-02-16 04:35 277阅读 0赞

单点更新

#include <iostream>
    using namespace std;
    const int MAX_N = 10010;
    int s[4*MAX_N];
    
    void up(int p){
        s[p] = s[p*2] + s[p*2+1];
    }
    
    void modify(int p,int l,int r,int x,int v){
        //x为要修改的叶子结点的左端点
        if(l == r){
            s[p] += v;
            return;
        }
        int mid = (l + r) / 2;
        if(x <= mid){
           modify(p*2,l,mid,x,v);    
        }else{
           modify(p*2+1,mid+1,r,x,v);
        }
        up(p);
    }
    
    int query(int p,int l,int r,int x,int y){  //x,y为要查询的区间
        if(x <= l && r <= y){
            return s[p];
        }
        int mid = (l + r) / 2, res = 0;  
        if(x <= mid){
            res += query(p*2,l,mid,x,y);
        }
        if(y > mid){
            res += query(p*2+1,mid+1,r,x,y);
        }
        return res;
    }
    
    int main() {
        int n;
        cin >> n;
        for(int i = 1; i <= n; ++i){
            int d;
            cin >> d;
            modify(1,1,n,i,d);
        }
        int q;
        cin >> q;
        while(q--){
            int d,x,y;
            cin >> d >> x >> y;
            if(d == 0){
                modify(1,1,n,x,y);
            }else{
                cout<<query(1,1,n,x,y)<<endl;
            }
            
        }
        return 0;
    }

区间更新

#include <iostream>
    using namespace std;
    const int MAX_N = 10010;
    int s[4*MAX_N],col[4*MAX_N];
    
    void up(int p){
        s[p] = s[p*2] + s[p*2+1];
    }
    
    void down(int p,int l,int r){
        if(col[p]){
            int mid = (l + r) / 2;   
            s[p*2] += col[p] * (mid - l + 1);
            s[p*2+1] += col[p] * (r - mid);
            col[p*2] += col[p];
            col[p*2+1] += col[p];
            col[p] = 0;
        }
    }
    
    void modify(int p,int l,int r,int x,int y,int c){
        if(x <= l && r <= y){
            s[p] += (r - l + 1) * c;
            col[p] += c;
            return;
        }
        down(p,l,r);
        int mid = (l + r) / 2;
        if(x <= mid){
            modify(p*2,l,mid,x,y,c);
        }
        if(y > mid){
            modify(p*2+1,mid+1,r,x,y,c);
        }
        up(p);
    }
    
    int query(int p,int l,int r,int x,int y){
        if(x <= l && r <= y){
            return s[p];
        }
        down(p,l,r);
        int mid = (l + r)/2,res = 0;
        if(x <= mid){
             res += query(p*2,l,mid,x,y);
        }
        if(y > mid){
             res += query(p*2+1,mid+1,r,x,y);
        }
        return res;
    }
    
    int main() {
        int n;
        cin >> n;
        for(int i = 1; i <= n; ++i){
            int d;
            cin >> d;
            modify(1,1,n,i,i,d);
        }
        int q;
        cin >> q;
        while(q--){
            int d,x,y,c;
            cin >> d >> x >> y;
            if(d == 0){
                cin >> c;
                modify(1,1,n,x,y,c);
            }else{
                cout<<query(1,1,n,x,y)<<endl;
            }
            
        }
        
        return 0;
    }