线段树小结

基本概念

线段树是一颗二叉树，每一个结点维护一段区间。因为是二叉树，所以可以用p*2表示p的左儿子，p*2+1表示p的右儿子。

struct node
{
    int l,r;//结点所维护的区间
    int num;//区间信息
}T[maxn<<2];//线段树要开四倍空间

建树

给定长度为n的数组a（下标从1开始）。
对区间[1,n]上的值建一颗线段树。

#define lson p*2
#define rson (p*2+1)
void up(int p)
{
    //区间信息的维护，将左子树所表示的区间与右子树所表示的区间合并
    T[p].num=max(T[lson].num,T[rson].num); //以维护最大值举例
}
void build(int p,int l,int r)//p表示结点编号，l、r表示结点p所表示的区间
{
    T[p].l=l,T[p].r=r;//确定结点p所表示的区间[l,r]
    if(l==r) //确定叶子结点所表示的信息
    {
        T[p].num=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid); //递归创建左子树
    build(rson,mid+1,r); //递归创建右子树
    up(p); //由下向上传递信息，即由两个小区间合并成一个大区间

}

单点修改

将第k个元素的值改为v。
递归找到叶子结点，修改叶子结点的值，然后用up函数向上修改包含该叶子结点的区间。

void update(int p,int k,int v)
{
    if(T[p].l==T[p].r) //找到叶子结点
    {
        T[p].num=v; //修改叶子结点信息
        return ;
    }
    int mid=(T[p].l+T[p].r)>>1;
    if(k<=mid) update(lson,k,v); //k叶子结点在左子树上
    else update(rson,k,v); //k叶子结点在右子树上
    up(p); //修改包含结点的区间
}

区间查询

查询区间[x,y]的信息。
将区间[x,y]分成若干小份区间，每一个区间恰好与线段树上某一个结点所表示的区间对应，获取该结点的信息并最终将若干个小份区间信息整理即可。

#define inf 0x3f3f3f3f
int query(int p,int x,int y)
{
    if(x==T[p].l && y=T[p].r) //区间[x,y]恰好与结点p所表示的区间重合
        return T[p].num;//这个结点所表示的区间信息是所需要的
    //down(p);
    ///注意：如果是区间修改的话，递归进子树调用信息前先要下传延迟标记
    int mid=(T[p].l+T[p].r)>>1;
    int ans=-inf;
    if(y<=mid) //区间[x,y]一定在p的左子树上
        return max(ans,query(lson,x,y));
    else if(x>mid) //区间[x,y]一定在p的右子树上
        return max(ans,query(rson,x,y));
    else //没有与区间[x,y]恰好重合的结点
    {
        //将区间[x,y]分成两个小区间[x,mid]和[mid+1,y]
        //[x,mid]一定在p的左子树上
        //[mid+1,y]一定在p的右子树上
        ans=max(ans,query(lson,x,mid));
        ans=max(ans,query(rson,mid+1,y));
        return ans;
    }
}

区间修改

如果像单点修改一样去修改每一个叶子的话，时间复杂度无法接受。所以引入延迟标记mark的概念。
比如说要修改区间[x,y]，恰好一个结点p所表示的区间就是[x,y]，那么修改了p的信息就够了，p的子树的结点信息暂不修改。但是仅仅是暂时不修改，当你需要去查询或者修改p的子树结点的信息时，就要先根据延迟标记mark修改了信息后再进行其他操作。

void update(int p,int x,int y,int v)
{
    if(T[p].l==x && T[p].r==y) //区间恰好重合
    {
        T[p].mark=v; //标记信息修改到此结点打止
        T[p].num=v; //修改信息
        return ;
    }
    //区间在p的子树结点中，要调用子树结点信息，必须先下传延迟标记
    down(p); //下传标记将p的左右子结点修改，只修改了这两个结点，延迟标记放在了这两个结点上
    int mid=(T[p].l+T[p].r)>>1;
    if(y<=mid) //区间[x,y]一定在左子树上
        update(lson,x,y,v);
    else if(x>mid) //区间[x,y]一定在右子树上
        update(rson,x,y,v);
    else
    {
        //必须将区间分成两份小区间[x,mid]和[mid+1,y]
        update(lson,x,mid,v);
        update(rson,mid+1,y,v);
    }
    up(p); 
}