带懒标记的线段树代码模板 → 区间更新、区间查询

【算法分析】
若利用线段树实现区间查询，需设计带懒标记的线段树。
懒标记的作用，通俗来讲就是利用线段树进行区间更新前先做标记，在用到有标记的地方时再更新，而不必一更到底。从而保证线段树区间更新操作的时间复杂度为O(logn)。
带懒标记的线段树代码与不带懒标记的代码的差别微乎其微。大家可与不带懒标记的线段树代码做一下比较。

【算法代码】

#include
using namespace std;

const int maxn=100005;
const int inf=0x3f3f3f3f;
int a[maxn];

struct node {
    int le,ri,mx,lz; //lz:懒标记
} tree[maxn*4];

void lazy(int k,int v) {
    tree[k].mx=v; //更新最值
    tree[k].lz=v; //做懒标记
}

void pushdown(int k) { //向下传递懒标记
    lazy(2*k,tree[k].lz); //传递给左孩子
    lazy(2*k+1,tree[k].lz); //传递给右孩子
    tree[k].lz=-1; //清除自己的懒标记
}

void build(int k,int le,int ri) { //创建线段树
    tree[k].le=le;
    tree[k].ri=ri;
    tree[k].lz=-1; //初始化懒操作
    if(le==ri) {
        tree[k].mx=a[le];
        return;
    }
    int mid,lson,rson;
    mid=(le+ri)/2;
    lson=k*2;
    rson=k*2+1;
    build(lson,le,mid);
    build(rson,mid+1,ri);
    tree[k].mx=max(tree[lson].mx,tree[rson].mx);
}

void update(int k,int le,int ri,int v) { //区间更新：将结点k所表示区间[le..ri]的所有元素都更新为v
    if(tree[k].le>=le && tree[k].ri<=ri) //找到该区间
        return lazy(k,v); //更新并做懒标记
    if(tree[k].lz!=-1) pushdown(k); //懒标记下移
    int mid,lson,rson;
    mid=(tree[k].le+tree[k].ri)/2;
    lson=k*2;
    rson=k*2+1;
    if(le<=mid) update(lson,le,ri,v); //到左子树更新
    if(ri>mid) update(rson,le,ri,v); //到右子树更新
    tree[k].mx=max(tree[lson].mx,tree[rson].mx);
}

int query(int k,int le,int ri) { //区间查询：求结点k所表示区间[le..ri]的最值
    if(tree[k].le>=le && tree[k].ri<=ri) //找到该区间
        return tree[k].mx;
    if(tree[k].lz!=-1) pushdown(k); //懒标记下移
    int mid,lson,rson;
    mid=(tree[k].le+tree[k].ri)/2;
    lson=k*2;
    rson=k*2+1;
    int iMAX=-inf;
    if(le<=mid)
        iMAX=max(iMAX,query(lson,le,ri));
    if(ri>mid)
        iMAX=max(iMAX,query(rson,le,ri));
    return iMAX;
}

void print(int k) {
    if(tree[k].mx) {
        cout<>n;
    for(int i=1; i<=n; i++) cin>>a[i];

    build(1,1,n); //创建线段树
    print(1);

    int le,ri;
    cout<<"Enter the query interval [le..ri]:"<>le>>ri;
    cout<>le>>ri>>v;
    update(1,le,ri,v);

    cout<<"Enter the query interval [le..ri] after updating:"<>le>>ri;
    cout< 


【参考文献】
 https://blog.csdn.net/hnjzsyjyj/article/details/120590584