线段树

一、线段树的实现

线段树可以通过指针实现 也可以通过数组实现。

二、线段树的更新

1、区间更新（普通方法）

void pushup(int rt)
{
    mx[rt]=max(mx[rt*2],mx[rt*2+1]);   //求最大值
}
void update(int L,int R,int l,int r,int rt)
{
    int mid = (l+r)/2;
    if(l == r)
    {
        执行要修改的内容
        return;
    }
    if(l == L&&r == R)
    {
        update(L, mid, l,mid, rt*2);
        update(mid+1, R, mid+1, r, rt*2+1);
    }
    else if(R <= mid)
    {
        update(L, R, l, mid, rt*2);
    }
    else if(L > mid)
    {
        update(L,R, mid+1, r, rt*2);
    }
    else if(L<= mid &&R> mid)
    {
        update(L, mid, l, mid, rt*2);
        update(mid+1,R ,mid+1, r, rt*2+1);

    }
    pushup(rt);//回溯时更新父亲的值
}