線段樹模闆整理

線段樹模闆

以前寫的線段樹很醜，看不下去，跟新過一版，還是醜。重新整理一份最新的了解，個人比較舒服，來跟新一下。以區間求和，區間更新為例，參考題目：poj 3468

題目連結：http://poj.org/problem?id=3468

代碼：

#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;//題目描述n
struct node {
    int l,r;//節點表示範圍l~r
    ll sum,lazy;//sum節點屬性,lazy跟新延遲标記
    inline int len() {
        return r-l+1;
    }
    inline void update(int val) {
        lazy+=val;
        sum+=1LL*len()*val;//1LL防止int溢出，轉為ll
    }
}tr[maxn*4];
int a[maxn];
//回溯跟新
void push_up(int id) {
    tr[id].sum=tr[id<<1].sum+tr[id<<1|1].sum;
}
//下放标記
void push_down(int id) {
    ll lazy=tr[id].lazy;
    if(lazy==0) return;
    tr[id<<1].update(lazy);
    tr[id<<1|1].update(lazy);
    tr[id].lazy=0;
}
//建立線段樹
void build(int id, int l, int r) {
    tr[id].l=l;tr[id].r=r;
    tr[id].lazy=tr[id].sum=0;
    if(l==r) {
        tr[id].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    push_up(id);//建立的過程中順帶區間統計
}
//跟新線段樹
void update(int id, int l, int r ,int val) {
    if(tr[id].l==l&&tr[id].r==r) {
        tr[id].update(val);
        return;
    }
    push_down(id);
    int mid=(tr[id].l+tr[id].r)>>1;
    if(r<=mid) update(id<<1,l,r,val);
    else if(l>mid) update(id<<1|1,l,r,val);
    else {
        update(id<<1,l,mid,val);
        update(id<<1|1,mid+1,r,val);
    }
    push_up(id);
}
ll query(int id, int l, int r) {
    if(tr[id].l==l&&tr[id].r==r) {
        return tr[id].sum;
    }
    push_down(id);
    int mid=(tr[id].l+tr[id].r)>>1;
    if(r<=mid) return query(id<<1,l,r);
    else if(l>mid) return query(id<<1|1,l,r);
    else return query(id<<1,l,mid)+query(id<<1|1,mid+1,r);
}
int main() {
    int n,q;
    char op[10];
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    build(1,1,n);
    for(int i=1;i<=q;++i) {
        scanf("%s",op);
        if(op[0]=='Q') {
            int l,r;
            scanf("%d %d",&l,&r);
            printf("%lld
",query(1,l,r));
        } else {
            int l,r,val;
            scanf("%d %d %d",&l,&r,&val);
            update(1,l,r,val);
        }
    }
    return 0;
}