线段树总结

学了一段时间的线段树、始终没有没有形成自己的风格、于是重头再来一遍、以HH大牛的线段树分类、单点更新、成段更新、区间合并、扫描线、重新梳理一遍自己的线段树知识、

单点更新：【HDU 1166 敌兵布阵】

分析：单点更新还是挺容易的、就是建立一颗二叉树、用来表示区间、可以优化查询时间和更新时间、

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std;  
#define lson l,mid,rt<<1  
#define rson mid+1,r,rt<<1|1  
const int maxn=55555;  
struct segmentTree{  
    int sum;  
}tree[maxn<<2];  
int per[maxn];  
void PushUp(int rt){  
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;  
}  
void build(int l,int r,int rt){  
    if(l==r){  
        tree[rt].sum=per[l];  
        return;  
    }  
    int mid=(l+r)/2;  
    build(lson);  
    build(rson);  
    PushUp(rt);  
}  
void update(int x,int add,int l,int r,int rt){  
    if(l==r){  
        tree[rt].sum+=add;  
        return;  
    }  
    int mid=(l+r)/2;  
    if(x<=mid)update(x,add,lson);  
    else update(x,add,rson);  
    PushUp(rt);  
}  
int query(int a,int b,int l,int r,int rt){  
    if(a<=l&&b>=r){  
        return tree[rt].sum;  
    }  
    int ans=0;  
    int mid=(l+r)/2;  
    if(a<=mid) ans+=query(a,b,lson);  
    if(b>mid) ans+=query(a,b,rson);  
    return ans;  
}  
int main(){  
    int t,n,cas=1;  
    scanf("%d",&t);  
    while(t--){  
        scanf("%d",&n);  
        printf("Case %d:\n",cas++);  
        for(int i=1;i<=n;i++){  
            scanf("%d",&per[i]);  
        }  
        build(1,n,1);  
        char op[11];  
        while(scanf("%s",op)!=EOF){  
            if(strcmp(op,"End")==0)break;  
            if(strcmp(op,"Query")==0){  
                int a,b;  
                scanf("%d%d",&a,&b);  
                printf("%d\n",query(a,b,1,n,1));  
            }  
            else if(strcmp(op,"Add")==0){  
                int a,b;  
                scanf("%d%d",&a,&b);  
                update(a,b,1,n,1);  
            }  
            else if(strcmp(op,"Sub")==0){  
                int a,b;  
                scanf("%d%d",&a,&b);  
                update(a,-b,1,n,1);  
            }  
        }  
    }  
    return 0;  
}

成段更新：【HDU 1698 Just a Hook】

分析：成段更新稍微复杂一点、其实也就是多个延迟标记、一次不更新到底、为什么不更新到底呢、还不是为了节约时间、等到下次需要向下更新或者查询的时候、就向下更新、这样貌似复杂度要低许多、

#include<stdio.h>  
#define lson l,mid,rt<<1  
#define rson mid+1,r,rt<<1|1  
#define maxn 100005  
struct segmentTree{  
    int sum;  
    int col;  
}tree[maxn<<2];  
void PushUp(int rt){  
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;  
}  
void build(int l,int r,int rt){  
    tree[rt].col=0;  
    if(l==r){  
        tree[rt].sum=1;  
        return;  
    }  
    int mid=(l+r)/2;  
    build(lson);  
    build(rson);  
    PushUp(rt);  
}  
void PushDown(int rt,int len){  
    if(tree[rt].col){  
        tree[rt<<1].col=tree[rt<<1|1].col=tree[rt].col;  
        tree[rt<<1].sum=(len-len/2)*tree[rt].col;  
        tree[rt<<1|1].sum=(len/2)*tree[rt].col;  
        tree[rt].col=0;  
    }  
}  
void update(int a,int b,int c,int l,int r,int rt){  
    if(a<=l&&b>=r){  
        tree[rt].col=c;  
        tree[rt].sum=c*(r-l+1);  
        return;  
    }  
    PushDown(rt,r-l+1);  
    int mid=(l+r)/2;  
    if(a<=mid)update(a,b,c,lson);  
    if(b>mid)update(a,b,c,rson);  
    PushUp(rt);  
}  
int main(){  
    int t,n,m,cas=1;  
    scanf("%d",&t);  
    while(t--){  
        scanf("%d",&n);  
        build(1,n,1);  
        scanf("%d",&m);  
        int a,b,v;  
        for(int i=1;i<=m;i++){  
            scanf("%d%d%d",&a,&b,&v);  
            update(a,b,v,1,n,1);  
        }  
        printf("Case %d: The total value of the hook is %d.\n",cas++,tree[1].sum);  
    }  
    return 0;  
}

区间合并：待续

补充：软件开发 , C++ ,