跳到主要内容

线段树

线段树基本知识​

image.png

image.png

image.png

image.png

代码​

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define lc p<<1
#define rc p<<1|1
#define N 500005
int n,w[N];
struct node{
int l,r,sum;
}tr[N*4];

void pushup(int p){//向上更新
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void build(int p,int l,int r){//建树 
    tr[p]={l,r,w[l]};
    if(l==r) return; //是叶子则返回 
    int m=l+r>>1; //不是叶子则裂开 
    build(lc,l,m);
    build(rc,m+1,r);
    pushup(p);
}
void update(int p,int x,int k){//点修改 
    if(tr[p].l==x&&tr[p].r==x){//叶子则修改 
        tr[p].sum+=k;
        return;
    }
    int m=tr[p].l+tr[p].r>>1;//非叶子则裂开 
    if(x<=m) update(lc,x,k);
    if(x>m) update(rc,x,k);
    pushup(p);
}
int query(int p,int x,int y){//区间查询 
    if(x<=tr[p].l&&tr[p].r<=y)//覆盖则返回 
        return tr[p].sum;
    int m=tr[p].l+tr[p].r>>1;//不覆盖则裂开 
    int sum=0;
    if(x<=m) sum+=query(lc,x,y);
    if(y>m) sum+=query(rc,x,y);
    return sum;
}
int main(){
    ios::sync_with_stdio(0);
    int m,op,x,y;  
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);

    while(m--){
        cin>>op>>x>>y;
        if(op==1) update(1,x,y);
        else cout<<query(1,x,y)<<endl;
    }
    return 0;
}

代码2，区间修改和查询​

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) printf("a[%d]=%d\n",x,a[x]);
#define pr(x) printf("x=%d\n",x);
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define lc p<<1
#define rc p<<1|1



typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

#define int LL

int n;
int w[N];
struct node{
    int l,r,sum;
    int add;//懒标记
}tr[N*4];


//向上更新
void pushup(int p){
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}

//向下更新
void pushdown(int p){
    //add为懒标记
    if (tr[p].add){
        tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1);
        tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1);
        tr[lc].add+=tr[p].add;
        tr[rc].add+=tr[p].add;
        tr[p].add=0;
    }
}

//构建
void build(int p,int l,int r){
    tr[p]={l,r,w[l]};
    if (l==r) return;
    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(p);
}

//单点修改
void update(int p,int x,int k){
    if (tr[p].l==x&&tr[p].r==x){
        tr[p].sum+=k;
        return;
    }
    int mid=tr[p].l+tr[p].r>>1;
    if (x<=mid) update(lc,x,k);
    else update(rc,x,k);
    pushup(p);
}

//区间查询
int query(int p,int x,int y){
    if (x<=tr[p].l&&tr[p].r<=y){
        return tr[p].sum;
    }
    int mid=tr[p].l+tr[p].r>>1;
    pushdown(p);
    int sum=0;
    if (x<=mid)sum+= query(lc,x,y);
    if (y>mid) sum+= query(rc,x,y);
    return sum;
}



//区间修改
void update(int p,int x,int y,int k){
    if (x<=tr[p].l&&tr[p].r<=y){
        tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
        tr[p].add+=k;
        return;
    }
    int m=tr[p].l+tr[p].r>>1;
    pushdown(p);
    if (x<=m) update(lc,x,y,k);
    if (y>m) update(rc,x,y,k);
    pushup(p);
}


signed main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
    while (m--){
        int op;
        cin>>op;
        if (op==1){
            int x,y,k;
            cin>>x>>y>>k;
            update(1,x,y,k);
        }else{
            int x,y;
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
    }


    return 0;
}

0%