2015-team4/seg_tree

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
void build(int p,int l,int r){
    if (l==r){
        tr[p]=1;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tr[p]=tr[p*2]+tr[p*2+1];
}

void insert(int p,int l,int r,int a,int x){
    int mid=(l+r)/2;
    if (l==r && r==a){
        tr[p]=max(tr[p],x);
        return;
    }
    if (a<=mid) insert(p*2,l,mid,a,x);
    else insert(p*2+1,mid+1,r,a,x);
    tr[p]=max(tr[p*2],tr[p*2+1]);
}

int get_max(int p,int l,int r,int a,int b){
    int mid=(l+r)/2;
    if (l==a && r==b) return tr[p];

    if (b<=mid) return get_max(p*2,l,mid,a,b);
    else if (a>mid) return get_max(p*2+1,mid+1,r,a,b);
    else{
        int t1=get_max(p*2,l,mid,a,mid);
        int t2=get_max(p*2+1,mid+1,r,mid+1,b);
        return max(t1,t2);
    }
}
}}}

void build(int p,int l,int r){
    if (l==r){
        tr[p]=1;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tr[p]=tr[p*2]+tr[p*2+1];
}
void insert(int p,int l,int r,int a,int x){
    int mid=(l+r)/2;
    if (l==r && r==a){
        tr[p]=max(tr[p],x);
        return;
    }
    if (a<=mid) insert(p*2,l,mid,a,x);
    else insert(p*2+1,mid+1,r,a,x);
    tr[p]=max(tr[p*2],tr[p*2+1]);
}
int get_max(int p,int l,int r,int a,int b){
    int mid=(l+r)/2;
    if (l==a && r==b) return tr[p];
    if (b<=mid) return get_max(p*2,l,mid,a,b);
    else if (a>mid) return get_max(p*2+1,mid+1,r,a,b);
    else{
        int t1=get_max(p*2,l,mid,a,mid);
        int t2=get_max(p*2+1,mid+1,r,mid+1,b);
        return max(t1,t2);
    }
}