[tem]线段树练习

1080 线段树练习

单点修改，区间查询和

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define m ((l+r)>>1)

#define lson o<<1,l,m

#define rson o<<1|1,m+1,r

#define lc o<<1

#define rc o<<1|1

using namespace std;

typedef long long ll;

const int N=1e5+,INF=1e9+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,a[N],M,op,x,y;

int t[N<<];

void build(int o,int l,int r){

    if(l==r) t[o]=a[l];

    else{

        build(lson);

        build(rson);

        t[o]=t[lc]+t[rc];

    }

}

void add(int o,int l,int r,int p,int v){

    if(l==r) t[o]+=v;

    else{

        if(p<=m) add(lson,p,v);

        else add(rson,p,v);

        t[o]=t[lc]+t[rc];

    }

}

int query(int o,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr) return t[o];

    else{

        int ans=;

        if(ql<=m) ans+=query(lson,ql,qr);

        if(qr>m) ans+=query(rson,ql,qr);

        return ans;

    }

}

int main(int argc, const char * argv[]) {

    n=read();

    for(int i=;i<=n;i++) a[i]=read();

    build(,,n);

    M=read();

    for(int i=;i<=M;i++){

        op=read();x=read();y=read();

        if(op==){add(,,n,x,y);}

        else {printf("%d\n",query(,,n,x,y));}

    }

    return ;

}

PS:树状数组

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int N=1e5+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,Q,a[N],c[N],flag,l,r,x;

inline int lowbit(int x){return x&-x;}

void build(int n){

    for(int i=;i<=n;i++){

        c[i]+=a[i];

        if(i+lowbit(i)<=n)

            c[i+lowbit(i)]+=c[i];

    }

}

void add(int x,int d){

    for(int i=x;i<=n;i+=lowbit(i)) c[i]+=d;

}

int sum(int x){

    int res=;

    for(int i=x;i>;i-=lowbit(i)) res+=c[i];

    return res;

}

int main(int argc, const char * argv[]) {

    n=read();

    for(int i=;i<=n;i++) a[i]=read();

    build(n);

    Q=read();

    for(int i=;i<=Q;i++){

        flag=read();

        if(flag==){

            l=read();x=read();add(l,x);

        }else{

            l=read();r=read();

            printf("%d\n",sum(r)-sum(l-));

        }

    }

    return ;

}

---

---

1082 线段树练习 3

区间修改，区间查询和

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define m (l+r)/2

#define lson o<<1,l,m

#define rson o<<1|1,m+1,r

#define lc o<<1

#define rc o<<1|1

using namespace std;

typedef long long ll;

const int N=2e5+,INF=1e9+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

struct node{

    ll lazy,x;

}t[N<<];

int a[N];

void build(int o,int l,int r){

    if(l==r) t[o].x=a[l];

    else{

        build(lson);

        build(rson);

        t[o].x=t[lc].x+t[rc].x;

    }

}

void paint(int o,int l,int r,ll delta){

    t[o].lazy+=delta;

    t[o].x+=delta*(r-l+);

}

void pushDown(int o,int l,int r){

    paint(lson,t[o].lazy);

    paint(rson,t[o].lazy);

    t[o].lazy=;

}

void add(int o,int l,int r,int ql,int qr,ll v){

    if(ql<=l&&r<=qr) paint(o,l,r,v);

    else{

        pushDown(o,l,r);

        if(ql<=m) add(lson,ql,qr,v);

        if(m<qr) add(rson,ql,qr,v);

        t[o].x=t[lc].x+t[rc].x;

    }

}

ll query(int o,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr) return t[o].x;

    else{

        pushDown(o,l,r);

        ll ans=;

        if(ql<=m) ans+=query(lson,ql,qr);

        if(m<qr) ans+=query(rson,ql,qr);

        return ans;

    }

}

int n,Q,flag,l,r,x;

int main(){

    n=read();

    for(int i=;i<=n;i++) a[i]=read();

    build(,,n);

    Q=read();

    for(int i=;i<=Q;i++){

        flag=read();

        if(flag==){

            l=read();r=read();x=read();

            add(,,n,l,r,x);

        }else{

            l=read();r=read();

            printf("%lld\n",query(,,n,l,r));

        }

    }

}