线段树相关

佚名 6年前 (2019-04-21) 随笔 537人围观抢沙发百度已收录

线段树

下面是一个简易模板，用数组实现线段树，可以轻易求出区间和以及修改某个位置的值。

P.S. 这是我在B站学了灯神的......链接在这里 (https://www.bilibili.com/video/av47331849" 【数据结构】线段树（Segment Tree） "){:target="_blank"}

#include<bits/stdc++.h>
using namespace std;

#define max_len 1000

void build_tree(int arr[],int tree[],int node,int start,int end){
    
    if(start == end){
        tree[node] = arr[start];
    }
    else {
        int mid=start+end;mid=mid/2;
        int left_node  = 2 * node + 1 ;
        int right_node = 2 * node + 2 ;
    
        build_tree(arr, tree, left_node,  start,   mid );
        build_tree(arr, tree, right_node, mid + 1, end );
        tree[node] = tree[left_node] + tree[right_node];
    }
}

void update_tree(int arr[],int tree[],int node,int start,int end,int idx ,int val){
    
    if(start == end){
        arr[idx]=val;
        tree[node]=val;
        
    }
    else {
        int mid=start+end;mid=mid/2;
        int left_node  = 2 * node + 1 ;
        int right_node = 2 * node + 2 ;
        if(idx>=start&&idx<=mid){
            update_tree(arr,tree,left_node,start,mid,idx,val);
        }
        else {
            update_tree(arr,tree,right_node,mid+1,end,idx,val);
        }
        tree[node] = tree[left_node] + tree[right_node];
    }
}

int sum_tree(int arr[], int tree[], int node, int start, int end, int L, int R){
    if(R<start||L>end){
        return 0;
    }
    else if(start==end){
        return tree[node];
    }else if(L<=start&&end<=R){
        return tree[node];
    }
    else {
        int mid=(start+end)/2;
        int left_node=mid+1;
        int right_node=mid+2;
        int sum_left=sum_tree(arr,tree,left_node,start,mid,L,R);
        int sum_right=sum_tree(arr,tree,right_node,mid+1,end,L,R);
        return sum_left+sum_right;
    }
}

int main(){
    int arr[]={1, 3, 5, 7, 9, 11};
    int size = 6;
    int tree[max_len ]={0};
    build_tree(arr, tree, 0, 0, size-1 );
    for(int i=0;i<15;i++)printf("tree %d = %d\n",i ,tree[i]);
    printf("\n");
    update_tree(arr,tree,0,0,size-1,4,6);
    for(int i=0;i<15;i++)printf("tree %d = %d\n",i ,tree[i]);
    printf("\n");
    int s=sum_tree(arr,tree,0,0,size-1,2,5);
    printf("%d",s);
}

现在来看一个实训题目

这里要求区间最大值和最小值的平均数（保留到整数）并且要多次修改某一个值

不难想到要线段树上场，不然时间会炸（别问我怎么知道的）

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

    #include<bits/stdc++.h>
    using namespace std;
    
    #define max_len 10000000
    int minn=100,maxx=0; 
    int arr[1005000]={0};
    int bigtree[max_len]={0},smatree[max_len]={0};
    
    void build_bigtree(int arr[],int tree[],int node,int start,int end){
        
        if(start == end){
            tree[node] = arr[start];
        }
        else {
            int mid=start+end;mid=mid/2;
            int left_node  = 2 * node + 1 ;
            int right_node = 2 * node + 2 ;
        
            build_bigtree(arr, tree, left_node,  start,   mid );
            build_bigtree(arr, tree, right_node, mid + 1, end );
            tree[node] =max( tree[left_node] ,tree[right_node]);
        }
    }
    
    void build_smatree(int arr[],int tree[],int node,int start,int end){
        
        if(start == end){
            tree[node] = arr[start];
        }
        else {
            int mid=start+end;mid=mid/2;
            int left_node  = 2 * node + 1 ;
            int right_node = 2 * node + 2 ;
        
            build_smatree(arr, tree, left_node,  start,   mid );
            build_smatree(arr, tree, right_node, mid + 1, end );
            tree[node] = min(tree[left_node] , tree[right_node]);
        }
    }
    
    void update_bigtree(int arr[],int tree[],int node,int start,int end,int idx ,int val){
        if(start == end){
            arr[idx]=val;
            tree[node]=val;
        }
        else {
            int mid=start+end;mid=mid/2;
            int left_node  = 2 * node + 1 ;
            int right_node = 2 * node + 2 ;
            if(idx>=start&&idx<=mid){
                update_bigtree(arr,tree,left_node,start,mid,idx,val);
            }
            else {
                update_bigtree(arr,tree,right_node,mid+1,end,idx,val);
            }
            tree[node] = max(tree[left_node] , tree[right_node]);
        }
    }
    
    void update_smatree(int arr[],int tree[],int node,int start,int end,int idx ,int val){
        if(start == end){
            arr[idx]=val;
            tree[node]=val;
        }
        else {
            int mid=start+end;mid=mid/2;
            int left_node  = 2 * node + 1 ;
            int right_node = 2 * node + 2 ;
            if(idx>=start&&idx<=mid){
                update_smatree(arr,tree,left_node,start,mid,idx,val);
            }
            else {
                update_smatree(arr,tree,right_node,mid+1,end,idx,val);
            }
            tree[node] =min(tree[left_node] , tree[right_node]);
        }
    }
    
    void sum_bigtree(int arr[], int tree[], int node, int start, int end, int L, int R){
    //  printf("maxn=%d\n",maxx);
        if(R<start||L>end){
            return ;
        }else if(L<=start&&end<=R){
            if(tree[node]>maxx)maxx=tree[node];
            return ;
        }else if(start==end){
                if(tree[node]>maxx)maxx=tree[node];
                return ;
        }
        else {
            int mid=(start+end)>>1;
            int left_node=2*node+1;
            int right_node=2*node+2;
            sum_bigtree(arr,tree,left_node,start,mid,L,R);
            sum_bigtree(arr,tree,right_node,mid+1,end,L,R);
        }
    }
    
    void sum_smatree(int arr[], int tree[], int node, int start, int end, int L, int R){
    //  printf("minn=%d\n",minn);
        if(R<start||L>end){
            return ;
        }else if(L<=start&&end<=R){
            if(tree[node]<minn)minn=tree[node];
            return ;
        }else if(start==end){
                if(tree[node]<minn)minn=tree[node];
                return ;
        }
        else {
            int mid=(start+end)/2;
            int left_node=2*node+1;
            int right_node=2*node+2;
            sum_smatree(arr,tree,left_node,start,mid,L,R);
            sum_smatree(arr,tree,right_node,mid+1,end,L,R);
        }
    }
    
    int main(){
        int n,q;
        scanf("%d %d",&n,&q);
        int size = n;
        for(int i=0;i<n;i++)scanf("%d",&arr[i]);
        
        build_bigtree(arr, bigtree, 0, 0, size-1 );
        build_smatree(arr, smatree, 0, 0, size-1 );
        
        for(int i=0;i<q;i++){
            int o1,o2,o3;
            minn=100,maxx=0; 
            scanf("%d %d %d",&o1,&o2,&o3);
            if(o1==0){
                sum_bigtree(arr,bigtree,0,0,size-1,o2-1,o3-1);
                sum_smatree(arr,smatree,0,0,size-1,o2-1,o3-1);
                int s=maxx+minn;
                printf("%d\n",s/2);
            }
            if(o1==1){
                update_bigtree(arr,bigtree,0,0,size-1,o2-1,o3);
                update_smatree(arr,smatree,0,0,size-1,o2-1,o3);
            }
        }
        return 0;
    }