线段树模板（单点修改区间查询）

chenzhixuan2010 · 2024-05-14 13:21:58 · 个人记录

• 2 x y 查询 [x,y] 区间的和。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn],sg[maxn * 4];
namespace SEG{
    //Segment Tree
    void SEGbuild(int rt,int l,int r){
        if (l == r){
            sg[rt] = a[l];
            return ;
        }
        int mid = (l + r) >> 1;
        SEGbuild(rt * 2,l,mid);
        SEGbuild(rt * 2 + 1,mid + 1,r);
        sg[rt] = sg[rt * 2] + sg[rt * 2 + 1];
    }
    void SEGupdate(int rt,int l,int r,int pos,int x){
        if (l == r){
            sg[rt] = x;
            return ;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid){
            SEGupdate(rt * 2,l,mid,pos,x);
        }
        else{
            SEGupdate(rt * 2 + 1,mid + 1,r,pos,x);
        }
        sg[rt] = sg[rt * 2] + sg[rt * 2 + 1];
    }
    int SEGquery(int rt,int l,int r,int lpos,int rpos){
        if (l > rpos || r < lpos){
            return 0;
        }
        if (lpos <= l && r <= rpos){
            return sg[rt];
        }
        int mid = (l + r) >> 1;
        int x = SEGquery(rt * 2,l,mid,lpos,rpos);
        int y = SEGquery(rt * 2 + 1,mid + 1,r,lpos,rpos);
        return x + y;
    }
}

using namespace SEG;
signed main(){
    int n,m;
    cin>>n>>m;
    for (int i = 1;i <= n;i++){
        cin>>a[i];
    }
    SEGbuild(1,1,n);
    for (int i = 1;i <= m;i++){
        int o,p,q;
        cin>>o>>p>>q;
        if (o == 1){
            SEGupdate(1,1,n,p,q);
        }
        else{
            cout<<SEGquery(1,1,n,p,q)<<'\n';
        }
    }
    return 0;
}

namespace:

const int maxn = 1e5 + 5;
int a[maxn],sg[maxn * 4];
namespace SEG{
    //Segment Tree
    void SEGbuild(int rt,int l,int r){
        if (l == r){
            sg[rt] = a[l];
            return ;
        }
        int mid = (l + r) >> 1;
        SEGbuild(rt * 2,l,mid);
        SEGbuild(rt * 2 + 1,mid + 1,r);
        sg[rt] = sg[rt * 2] + sg[rt * 2 + 1];
    }
    void SEGupdate(int rt,int l,int r,int pos,int x){
        if (l == r){
            sg[rt] = x;
            return ;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid){
            SEGupdate(rt * 2,l,mid,pos,x);
        }
        else{
            SEGupdate(rt * 2 + 1,mid + 1,r,pos,x);
        }
        sg[rt] = sg[rt * 2] + sg[rt * 2 + 1];
    }
    int SEGquery(int rt,int l,int r,int lpos,int rpos){
        if (l > rpos || r < lpos){
            return 0;
        }
        if (lpos <= l && r <= rpos){
            return sg[rt];
        }
        int mid = (l + r) >> 1;
        int x = SEGquery(rt * 2,l,mid,lpos,rpos);
        int y = SEGquery(rt * 2 + 1,mid + 1,r,lpos,rpos);
        return x + y;
    }
}