线段树模板

一、建树

void build(int node, int left, int right)
{
    if(right == left){
        tree[node] = 1;
    }
    else{
        int left_node = 2*node;
        int right_node = 2*node + 1;
        int mid = (left+right) / 2;
        build(left_node,left,mid);
        build(right_node,mid+1,right);
        tree[node] = tree[right_node] + tree[left_node];
    }
}

二、单点修改

void Add(int node, int left , int right, int idx, int more)   //单点修改
{
    if(left == right)
        tree[node] += more;
    else{
        int mid = (left+right) / 2;
        int left_node = node*2 + 1;
        int right_node = node*2 + 2;
        if(idx <= mid){
            Add(left_node,left,mid,idx,more);
        }
        else if(idx > mid){
            Add(right_node,mid+1,right,idx,more);
        }
        tree[node] = tree[left_node] + tree[right_node];
    }
}

三、区间查询

ll check(int node,int left,int right,int search_left,int search_right)
{
     
    if(search_left >= left && search_right <= right)
        return p[node];
    int mid = (search_left + search_right) / 2;
    int left_node = node * 2;
    int right_node = node * 2 + 1;
    ll res=0;
    if(left <= mid)
        res+=check(left_node,left,right,search_left,mid);
    if(right > mid)
        res+=check(right_node,left,right,mid+1,search_right);
    return res;
}

四、区间修改

void putdown(int node, int left, int right){
    int left_node = 2*node;
    int right_node = 2*node + 1;   
    int mid = (left+right) / 2;
    tree[left_node] = up[node] * (mid - left + 1);
    tree[right_node] = up[node] * (right - mid);
    up[left_node] = up[node];
    up[right_node] = up[node];
    up[node] = 0;
}

void change(int node, int left, int right, int from, int end, int val)
{
    if(from <= left && end >= right){
        tree[node] = (right - left + 1) * val;
        up[node] = val;
        return;
    }
    if(up[node]){
        putdown(node,left,right);
    }
    int left_node = 2*node;
    int right_node = 2*node + 1;
    int mid = (left + right) / 2;
    if(from <= mid){
        change(left_node, left, mid, from, end, val);
    }
    if(end > mid){
        change(right_node,mid+1,right,from,end,val);
    }
    tree[node] = tree[left_node] + tree[right_node];
} 

五、求区间最大值

void build(int node, int left, int right)
{
    if(right == left){
        MAX[node] = a[left];
    }
    else{
        int left_node = 2*node;
        int right_ndoe = 2*node + 1;
        int mid = (left+right) / 2;
        build(left_node,left,mid);
        build(right_ndoe,mid+1,right);
        MAX[node] = max(MAX[left_node],MAX[right_ndoe]);
    }
}

void query(int node, int left, int right, int from, int end)
{
    if(left == from && right == end){
        sum = max(sum,MAX[node]);
    }
    else{
        int left_node = 2*node;
        int right_node = 2*node + 1;
        int mid = (left+right) / 2;
        if(from <= mid){
            query(left_node,left,mid,from,min(mid,end));
        }
        if(end > mid){
            query(right_node,mid+1,right,max(mid + 1,from),end);
        }        
    }
}