RMQ问题——线段树+懒标记

线段树，基于分治思想，用来维护区间信息的二叉树结构

例如RMQ，区间和，区间GCD问题，在平均 $O(\log n)$ 的时间复杂度内执行区间修改和查询操作

朴素的线段树的每个节点包含三个元素：左区间，右区间，区间元素统计值（以区间和为例）

struct node{
    int l,r,sum;
};

对于父节点的编号 $p$ ，左右孩子的编号即为 $2*p,2*p+1$

#define lc p<<1;//定义左儿子
#define rc p<<1|1//定义右儿子

建树时，采用递归的方式，自下而上赋值

node tr[4*N];
void build(int p,int l,int r){
    tr[p]={l,r,w[l]};//递归到底层，给叶子节点赋值，非叶子节点无效
    if (l==r) return;//递归出口
    int m=l+r>>1;//二分树
    build(lc,l,m);//递归建树左儿子
    build(rc,m+1,r);//递归建树右儿子
    tr[p].sum=tr[lc].sum+tr[rc].sum;//递归回溯，赋值非叶子节点的区间统计值
}

有关线段树为什么需要开 $4*N$ 空间的问题：

因为线段树不一定为满二叉树，所以对于区间 $[1,n]$ ，底层的叶子节点数最差情况为 $2^{\lfloor\log _2n\rfloor+1}$，所以总节点数最差为

$$ 2^{\lfloor\log _2n\rfloor+1}*2-1=4*n-1\approx4*n $$

针对区间某一点进行修改，采用递归的方式从树顶进入，到达目标叶子节点然后回溯更新非叶子节点

void update(int p,int x,int k){//p一开始为1，即从根节点进入 x为目标点，k为需要修改为的值
    if (tr[p].l==x&&tr[p].r==x){//到达需要修改的点
        tr[p].sum=k;//更新值
        return;
    }
    int m=tr[p].l+tr[p].r>>1;//分治
    if (x<=m) update(lc,x,k);//x在左半边
    else update(rc,x,k);//x在右半边
    tr[p].sum=tr[lc].sum+tr[rc].sum;//回溯更新非叶子节点的区间统计值
}

对某一区间进行统计值的查询，采取拆分和拼凑的办法

  • 如果二分下来的区间能被需要查询的区间完全覆盖，那么直接加上这个区间的统计值即可（拼凑答案的一部分）
  • 左儿子与需要查询的区间有重合，那就递归左子树
  • 右儿子与需要查询的区间有重合，那就递归右子树
int query(int p,int x,int y){
    if (x<=tr[p].l&&y>=tr[p].r)//能完全覆盖的区间一定是答案的一部分
        return tr[p].sum;
    int m=tr[p].l+tr[p].r>>1;
    int sum=0;
    if (x<=m) sum+=query(lc,x,y);//访问左子树
    if (y>m) sum+=query(rc,x,y);//访问右子树
    return sum;
}

懒惰修改：

修改区间时给非叶子节点添加懒标记，只在必要的条件下下传懒标记，否则一直维持在非叶子节点上

这个操作可以将朴素的区间修改操作的 $O(n)$ 优化到 $O(\log n)$

struct node{
    int l,r,sum,add;//额外增添懒标记
};
void build(int p,int l,int r){
    tr[p]={l,r,w[l],0};//建树时，初始化懒标记为0
    ...
}

下传懒标记，区间修改操作：

void pushdown(int p){//下传懒标记
    if (tr[p].add){
        tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1);//更新左儿子的统计值
        tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1);//更新右儿子的统计值
        tr[lc].add+=tr[p].add;//下传给左儿子
        tr[rc].add+=tr[p].add;//下传给右儿子
        tr[p].add=0;
    }
}

void update(int p,int x,int y,int k){//更新xy区间的值都增加k
    if (x<=tr[p].l&&y>=tr[p].r){//如果完全覆盖，直接修改非叶子节点统计值，添加懒标记
        tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
        tr[p].add+=k;
        return;
    }
    int m=tr[p].l+tr[p].r>>1;
    pushdown(p);//下传懒标记
    if (x<=m) update(lc,x,y,k);//维护左子树
    if (y>m) update(rc,x,y,k);//维护右子树
    tr[p].sum=tr[lc].sum+tr[rc].sum;//更新非叶子节点区间统计值
}

同样的，添加了懒标记后，区间查询操作仍然需要下传

int query(int p,int x,int y){
    if (x<=tr[p].l&&y>=tr[p].r)//能完全覆盖的区间一定是答案的一部分
        return tr[p].sum;
    int m=tr[p].l+tr[p].r>>1;
    pushdown(p);//下传懒标记
    int sum=0;
    if (x<=m) sum+=query(lc,x,y);//访问左子树
    if (y>m) sum+=query(rc,x,y);//访问右子树
    return sum;
}