zkw线段树

今天自己动手实现了一下zkw版线段树,做了两道小题.

zkw版线段树就是非递归版的线段树,易于理解,实现简单,速度快.

参考《统计的力量-线段树全接触.ppt》http://www.slideshare.net/DanielChou/ss-7792670

注意求M的地方:for(M=1;M<=n+1;M*=2);

和老言争论了半天的n后面是否+1(是否进行越界处理),后来得出的结论是:

+1,浪费空间;

不加,遇到特殊情况有安全隐患,但证明,对于t,如果为偶数,则不进行处理,所以,可以不加.

单点更新:

hdu1166-敌兵布阵(单点更新,区间求和)

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define N 50005
int M;
int T[N*4];
int Query(int s,int t){
    int ans=0;
    for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
        if(~s&1) ans+=T[s^1];//如果是左子树的左孩子,则处理左子树右孩子
        if( t&1) ans+=T[t^1];//如果是右子树的左孩子,则处理右子树左孩子
    }
    return ans;
}
void Add(int n,int V){
    for(T[n+=M]+=V,n>>=1;n;n>>=1){
        T[n]=T[n+n]+T[n+n+1];
    }
}
void Sub(int n,int V){
    for(T[n+=M]-=V,n/=2;n;n/=2){
        T[n]=T[n*2]+T[n*2+1];
    }
}
void build_tree(int n){
    int i;
    for(M=1;M<=n+1;M*=2)//计算M
    for(i=M+1;i<=M+n;i++){
        scanf("%d",&T[i]);
    }
    for(i=M-1;i>0;i--) T[i]=T[i*2]+T[i*2+1];

}

int main()
{
    int t,n,a,b,k=0;
    char str[10];
    scanf("%d",&t);
    while(t--){
        printf("Case %d:\n",++k);
        memset(T,0,sizeof(T));
        scanf("%d",&n);
        build_tree(n);
        while(1){
            scanf("%s",str);
            if(strcmp(str,"Query")==0){
                scanf("%d%d",&a,&b);
                cout << Query(a,b) << endl;
            }
            else if(strcmp(str,"Add")==0){
                scanf("%d%d",&a,&b);
                Add(a,b);
            }
            else if(strcmp(str,"Sub")==0){
                scanf("%d%d",&a,&b);
                Sub(a,b);
            }
            else if(strcmp(str,"End")==0){
                break;
            }
        }

    }
}

hdu1754-I Hate It(单点更新,区间最值)

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define N 200005
int T[N*4],M;

void seg_build(int n){
    int i;
    for(M=1;M<=n+1;M*=2);
    for(i=1+M;i<=n+M;i++){
        scanf("%d",&T[i]);
    }
    for(i=M-1;i;i--) T[i]=max(T[i*2],T[i*2+1]);
}

void seg_update(int n,int V){
    for(T[n+=M]=V,n/=2;n;n/=2)
        T[n]=max(T[n*2],T[n*2+1]);
}

int seg_query(int s,int t){
    int maxc=-1;
    for(s=s+M-1,t=t+M+1;s^t^1;s/=2,t/=2){
        if(s%2==0) maxc=max(maxc,T[s^1]);
        if(t%2==1) maxc=max(maxc,T[t^1]);
    }
    return maxc;
}

int main()
{
    int n,m,a,b;
    char str[5];
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(T,0,sizeof(T));
        seg_build(n);
        while(m--){
            scanf("%s%d%d",str,&a,&b);
            if(strcmp(str,"U")==0){
                seg_update(a,b);
            }
            else if(strcmp(str,"Q")==0){
                cout << seg_query(a,b) << endl;
            }
        }
    }
    return 0;
}

区间更新:

继续研读中...