banner
cos

cos

愿热情永存,愿热爱不灭,愿生活无憾
github
tg_channel
bilibili

RMQ问题——线段树

上篇说到 RMQ 问题可以用 ST 表算法处理,但需要在线修改的时候,线段树是更好的选择。
如图,很明显线段树是个二叉搜索树
在这里插入图片描述
要注意的点如下:

  1. 线段树用数组存储,数组空间简单的就一般开到原数组的 4*n 倍(准确的说是将 n 向上扩充到 2 的幂次方然后乘 2,如 5->8->16)
  2. 线段树数组存储中,某个结点的编号为 n,则其左子结点编号为 2 * n(表示成 n << 1),右子节点编号为 2*n+1 (表示为 n << 1 | 1)
  3. 规定根节点为 1

一、查询区间最值(点修改)#

模板题:hihoCoder #1077 RMQ 问题再临 - 线段树
题目大意:给出一个数组 A,每次有查询或修改两种操作,此处是查询区间 l 到 r 上的最小值,或将编号为 p 的值改为 v。
用线段树维护最值,想要改成查询最大值,只需把所有 min 改成 max,然后把 inf 换成 0

1. 建树#

void pushup(int rt) {//更新节点信息 这里以求最小值为例 可改为最大值
    Tree[rt] = min(Tree[rt << 1], Tree[rt << 1|1]);
}
void Build(int l, int r, int rt) {//[l,r]表示区间,rt表示真实存储的编号
    if (l == r) {//抵达叶结点
        Tree[rt] = A[l];
        return;
    }
    int mid = l+r>>1;
    Build(l,mid,rt << 1);//先建好左结点
    Build(mid+1,r,rt << 1 | 1);//再建好右节点
    pushup(rt);//用左右节点更新信息
}

2. 更新#

调用时参数为根节点编号、修改位置 p、要修改成的值 v、修改影响的区间(即 1~n)。

void Update_point(int rt, int p, int val, int l, int r) {   //点修改
    if (l == r) {
        Tree[rt] = val;
        return;
    }
    int mid = (l+r) >> 1;
    if (p <= mid)//修改的位置如果是在左半区间,则更新左子树
        Update_point(rt<<1, p, val, l, mid);
    else Update_point(rt<<1|1, p, val, mid+1, r);//否则更新右子树
    pushup(rt);//更新当前点~
}

3. 查询#

难点所在,调用时参数分别为根结点、整个区间 (1 ~ n)、要查询的区间 (x ~ y)
ps: 要查询的区间是要一直传下去不会变的~当要查询的区间子区间为 l ~ r 时即可返回

int query(int rt, int l, int r,int x, int y) {//从节点rt开始查询L到R的最小值/最大值/区间和 此处以最小值为例
    if (x <= l && r <= y) {//当l ~ r为要查询的区间的子区间时可直接返回当前结点的值
        return Tree[rt];
    }
    int mid = l+r >> 1;
    int ans = inf;//若求最大值,将此处改为0
    if (x <= mid) //若当前区间左端点小于等于mid,则肯定要查询左半区间
        ans = min(query(rt<<1,l,mid,x,y), ans);
    if (y > mid)//若当前区间右端点大于mid,则肯定要查询右半区间
        ans = min(query(rt<<1|1,mid+1,r,x,y), ans); 
    return ans;
}

完整代码#

#include <iostream>
#include <algorithm>
using namespace std;
//定义
const int maxn = 1000005;
const int inf  = 0x3f3f3f;
int Tree[maxn<<2];
int A[maxn];
int n;
void pushup(int rt) {//向上更新节点信息 这里以求最小值为例 可改为最大值
    Tree[rt] = min(Tree[rt << 1], Tree[rt << 1|1]);
}
void Build(int l, int r, int rt) {//[l,r]表示区间,rt表示真实存储的编号
    if (l == r) {//抵达叶结点
        Tree[rt] = A[l];
        return;
    }
    int mid = l+r>>1;
    Build(l,mid,rt << 1);//先建好左结点
    Build(mid+1,r,rt << 1 | 1);//再建好右节点
    pushup(rt);//用左右节点更新信息
}
void Update_point(int rt, int p, int val, int l, int r) {   //点修改
    if (l == r) {
        Tree[rt] = val;
        return;
    }
    int mid = (l+r) >> 1;
    if (p <= mid)//修改的位置如果是在左半区间,则更新左子树
        Update_point(rt<<1, p, val, l, mid);
    else Update_point(rt<<1|1, p, val, mid+1, r);//否则更新右子树
    pushup(rt);//更新当前点~
}
int query(int rt, int l, int r,int x, int y) {//从节点rt开始查询L到R的最小值/最大值/区间和 此处以最小值为例
    if (x <= l && r <= y) {//当l ~ r为要查询的区间的子区间时可直接返回当前结点的值
        return Tree[rt];
    }
    int mid = l+r >> 1;
    int ans = inf;//若求最大值,将此处改为0
    if (x <= mid) //若当前区间左端点小于等于mid,则肯定要查询左半区间
        ans = min(query(rt<<1,l,mid,x,y), ans);
    if (y > mid)//若当前区间右端点大于mid,则肯定要查询右半区间
        ans = min(query(rt<<1|1,mid+1,r,x,y), ans); 
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    Build(1,n,1);
    int T;
    cin >> T;
    while(T--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) {
            Update_point(1,b,c,1,n);
        } else {
            int ans = query(1,1,n,b,c);
            cout << ans << endl;
        }
    }
    return 0;
}

二、区间修改(和、差、积、商等)#

1. 区间加操作#

洛谷 P3372 【模板】线段树 1
大意为:已知一个数列,你需要进行下面两种操作:
1. 将某区间每一个数加上 kk。
2. 求出某区间每一个数的和。
大神题解
大神都写这么详细了我还写这个干嘛啊
算了算了自己敲一遍留着看也不错嘛
我们可以用线段树来维护区间和,以及修改的话是进行修改区间修改~这就需要一个标记数组标记,其实点修改就是区间修改的一个子问题

pushdown 操作#

向下更新,因为懒标记 add 记录了对其子结点的影响,所以需要一个向下传递影响的函数

inline void f(int rt, int l, int r, ll k) {//给当前结点加上k的影响,并更新其懒标记
    Tree[rt] += k * (r-l+1);//区间和 这里维护的是区间和,区间内每个数都加上k
    add[rt] += k;
}
void pushdown(int rt, int l, int r) {
    int mid = l+r >>1;
    f(rt<<1, l, mid, add[rt]);//更新左儿子的懒标记及其维护的值(区间和)
    f(rt<<1|1, mid+1, r, add[rt]);//更新右儿子的懒标记及其维护的值(区间和)
    add[rt] = 0;//当前懒标记置为0
}

更新区间#

void Update_section(int rt, int val, int l, int r, int rl, int rr) {   //区间修改
    if (rl <= l && r <= rr) {//~当前区间为要修改的区间的子区间时直接更新其值和懒标记~
        f(rt, l, r, val);
        return;
    }
    pushdown(rt, l, r);//下一次递归前,先将当前结点的影响向下传递,然后更新当前结点
    int mid = (l+r) >> 1;
    if (rl <= mid)//修改的区间如果能影响到左半区间,则更新左子树
        Update_section(rt<<1, val, l, mid, rl, rr);
    if (rr > mid)
        Update_section(rt<<1|1, val, mid+1, r, rl, rr);//否则更新右子树
    pushup(rt);//~向上更新~
}

完整代码#

#include <iostream>
#include <algorithm>
using namespace std;
//定义
typedef long long ll;
const int maxn = 1000005;
const int inf  = 0x3f3f3f;
ll add[maxn<<2];//懒标记 即对其所有子结点的影响 不包括其自身
ll Tree[maxn<<2];
ll A[maxn];
int n, T;
inline void pushup(int rt) {//向上更新节点信息 即用左孩子和右孩子的值来更新当前结点
    Tree[rt] = Tree[rt << 1]+Tree[rt << 1|1];
}
inline void f(int rt, int l, int r, ll k) {//给当前结点加上k的影响,并更新其懒标记
    Tree[rt] += k * (r-l+1);//区间和 这里维护的是区间和,区间内每个数都加上k
    add[rt] += k;
}
void pushdown(int rt, int l, int r) {
    int mid = l+r >>1;
    f(rt<<1, l, mid, add[rt]);//更新左儿子的懒标记及其维护的值(区间和)
    f(rt<<1|1, mid+1, r, add[rt]);//更新右儿子的懒标记及其维护的值(区间和)
    add[rt] = 0;//当前懒标记置为0
}
void Build(int l, int r, int rt) {//[l,r]表示区间,rt表示真实存储的编号
    add[rt] = 0;
    if (l == r) {//抵达叶结点
        Tree[rt] = A[l];
        return;
    }
    int mid = l+r>>1;
    Build(l,mid,rt << 1);//先建好左结点
    Build(mid+1,r,rt << 1 | 1);//再建好右节点
    pushup(rt);//用左右节点更新信息
}
void Update_section(int rt, int val, int l, int r, int rl, int rr) {   //区间修改
    if (rl <= l && r <= rr) {//~当前区间为要修改的区间的子区间时直接更新其值和懒标记~
        f(rt, l, r, val);
        return;
    }
    pushdown(rt, l, r);//下一次递归前,先将当前结点的影响向下传递,然后更新当前结点
    int mid = (l+r) >> 1;
    if (rl <= mid)//修改的区间如果能影响到左半区间,则更新左子树
        Update_section(rt<<1, val, l, mid, rl, rr);
    if (rr > mid)
        Update_section(rt<<1|1, val, mid+1, r, rl, rr);//否则更新右子树
    pushup(rt);//~向上更新~
}
ll query(int rt, int l, int r,int x, int y) {//从节点rt开始查询l到r的中x~y的区间和 此处以最小值为例
    if (x <= l && r <= y) {//当l ~ r为要查询的区间的子区间时可直接返回当前结点的值
        return Tree[rt];
    }
    int mid = l+r >> 1;
    ll ans = 0;
    pushdown(rt, l, r);
    if (x <= mid) //若当前区间左端点小于等于mid,则肯定要查询左半区间
        ans += query(rt<<1,l,mid,x,y);
    if (y > mid)//若当前区间右端点大于mid,则肯定要查询右半区间
        ans += query(rt<<1|1,mid+1,r,x,y); 
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> T;
    for(int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    Build(1,n,1);
    while(T--) {
        int a, l, r;
        cin >> a;
        if (a == 1) {
            int k;
            cin >> l >> r >> k;
            Update_section(1, k, 1, n, l, r);
        } else {
            cin >> l >> r;
            ll ans = query(1, 1, n, l, r);
            cout << ans << endl;
        }
    }
    return 0;
}

2. 区间加、乘操作(较完整)#

洛谷 P3373【模板】线段树 2
大神题解
这题就是在上一题的基础上变成可将某区间每个数乘 / 加上一个数,则需要两个懒标记数组 add、mul,而在更新懒标记操作中也要注意若要更新 add 标记则只更新 add,若要更新 mul 则更新 mul 的同时也必须更新 add(add 乘上 k)
先乘后加!!
先乘后加!!!
先乘后加!!!
重要的事情说三遍

pushdown 操作的变动#

主要是 f 函数的变动
注意到 f 函数的功能是给当前结点 rt 的值加上上一个结点 ft 的所有影响(懒标记带来的),并更新当前结点 ft 的懒标记

inline void f(int rt, int l, int r, int ft) {//给当前结点rt加上上一个结点ft的所有影响,更新其懒标记
    //先乘后加!!更新其值
    Tree[rt] = (Tree[rt] * mul[ft]) % p;
    Tree[rt] = (Tree[rt] + add[ft] * (r-l+1)) % p;
    //更新懒标记,mul直接更新(*父结点的mul)
    mul[rt] = (mul[rt] * mul[ft]) % p;
    //add应先*父结点的mul标记,然后再+父节点的add标记!!!
    add[rt] = (add[rt] * mul[ft]) % p;
    add[rt] = (add[rt] + add[ft]) % p;
}
void pushdown(int rt, int l, int r) {
    int mid = l+r >>1;
    f(rt<<1, l, mid, rt);//更新左儿子的懒标记及其维护的值
    f(rt<<1|1, mid+1, r, rt);//更新右儿子的懒标记及其维护的值
    add[rt] = 0;
    mul[rt] = 1;//当前懒标记
}

更新操作变动(分两种更新)#

加更新~

void Update_section_add(int rt,int val, int l, int r, int rl, int rr) {   //区间修改 +val
    if (rl <= l && r <= rr) {//~当前区间为要修改的区间的子区间时直接更新其值和懒标记~
        Tree[rt] =  (Tree[rt] + val * (r-l+1)) % p;//给当前结点加上val的+影响,并更新其懒标记
        add[rt] = (add[rt] + val) % p;
        return;
    }
    pushdown(rt, l, r);//下一次递归前,先将影响向下传递
    int mid = (l+r) >> 1;
    if (rl <= mid)//修改的区间如果能影响到左半区间,则更新左子树
        Update_section_add(rt<<1, val, l, mid, rl, rr);
    if (rr > mid)
        Update_section_add(rt<<1|1, val, mid+1, r, rl, rr);//否则更新右子树
    pushup(rt);//开始回溯~向上更新~
}

乘更新~乘会影响到加的懒标记!

void Update_section_mul(int rt,int val, int l, int r, int rl, int rr) {   //区间修改 *val
    if (rl <= l && r <= rr) {//~当前区间为要修改的区间的子区间时直接更新其值和懒标记~
        Tree[rt] = (Tree[rt] * val) % p;
        mul[rt] = (mul[rt] * val) % p;
        add[rt] = (add[rt] * val) % p;//very重要!!
        return;
    }
    pushdown(rt, l, r);//下一次递归前,先将影响向下传递
    int mid = (l+r) >> 1;
    if (rl <= mid)//修改的区间如果能影响到左半区间,则更新左子树
        Update_section_mul(rt<<1, val, l, mid, rl, rr);
    if (rr > mid)
        Update_section_mul(rt<<1|1, val, mid+1, r, rl, rr);//否则更新右子树
    pushup(rt);//开始回溯~向上更新~
}

完整代码#

#include <iostream>
#include <algorithm>
using namespace std;
//定义
typedef long long ll;
const int maxn = 1000005;
ll add[maxn<<2];//懒标记1 即对其所有子结点的影响 不包括其自身
ll mul[maxn<<2];//懒标记2
ll Tree[maxn<<2];
ll A[maxn];
int n, T;
ll p;
inline void pushup(int rt) {//向上更新节点信息 即用左孩子和右孩子的值来更新当前结点
    Tree[rt] = Tree[rt << 1]+Tree[rt << 1|1];
}
inline void f(int rt, int l, int r, int ft) {//给当前结点rt加上上一个结点ft的k的所有影响,更新其懒标记
    //先乘后加!!
    Tree[rt] = (Tree[rt] * mul[ft]) % p;
    Tree[rt] = (Tree[rt] + add[ft] * (r-l+1)) % p;
    //mul直接更新
    mul[rt] = (mul[rt] * mul[ft]) % p;
    //加的懒标记应先*父结点的mul标记,然后再+父节点的add标记!!!
    add[rt] = (add[rt] * mul[ft]) % p;
    add[rt] = (add[rt] + add[ft]) % p;
}
void pushdown(int rt, int l, int r) {
    int mid = l+r >>1;
    f(rt<<1, l, mid, rt);//更新左儿子的懒标记及其维护的值
    f(rt<<1|1, mid+1, r, rt);//更新右儿子的懒标记及其维护的值
    add[rt] = 0;
    mul[rt] = 1;//当前懒标记
}
void Build(int l, int r, int rt) {//[l,r]表示区间,rt表示真实存储的编号
    add[rt] = 0;
    mul[rt] = 1;
    if (l == r) {//抵达叶结点
        Tree[rt] = A[l];
        return;
    }
    int mid = l+r>>1;
    Build(l,mid,rt << 1);//先建好左结点
    Build(mid+1,r,rt << 1 | 1);//再建好右节点
    pushup(rt);//用左右节点更新信息
}
void Update_section_add(int rt,int val, int l, int r, int rl, int rr) {   //区间修改 +val
    if (rl <= l && r <= rr) {//~当前区间为要修改的区间的子区间时直接更新其值和懒标记~
        Tree[rt] =  (Tree[rt] + val * (r-l+1)) % p;//给当前结点加上val的+影响,并更新其懒标记
        add[rt] = (add[rt] + val) % p;
        return;
    }
    pushdown(rt, l, r);//下一次递归前,先将影响向下传递
    int mid = (l+r) >> 1;
    if (rl <= mid)//修改的区间如果能影响到左半区间,则更新左子树
        Update_section_add(rt<<1, val, l, mid, rl, rr);
    if (rr > mid)
        Update_section_add(rt<<1|1, val, mid+1, r, rl, rr);//否则更新右子树
    pushup(rt);//开始回溯~向上更新~
}
void Update_section_mul(int rt,int val, int l, int r, int rl, int rr) {   //区间修改 *val
    if (rl <= l && r <= rr) {//~当前区间为要修改的区间的子区间时直接更新其值和懒标记~
        Tree[rt] = (Tree[rt] * val) % p;
        mul[rt] = (mul[rt] * val) % p;
        add[rt] = (add[rt] * val) % p;//very重要!!
        return;
    }
    pushdown(rt, l, r);//下一次递归前,先将影响向下传递
    int mid = (l+r) >> 1;
    if (rl <= mid)//修改的区间如果能影响到左半区间,则更新左子树
        Update_section_mul(rt<<1, val, l, mid, rl, rr);
    if (rr > mid)
        Update_section_mul(rt<<1|1, val, mid+1, r, rl, rr);//否则更新右子树
    pushup(rt);//开始回溯~向上更新~
}
ll query(int rt, int l, int r,int x, int y) {//从节点rt开始查询l到r的中x~y的区间和 此处以最小值为例
    if (x <= l && r <= y) {//当l ~ r为要查询的区间的子区间时可直接返回当前结点的值
        return Tree[rt];
    }
    int mid = l+r >> 1;
    ll ans = 0;
    pushdown(rt, l, r);
    if (x <= mid) //若当前区间左端点小于等于mid,则肯定要查询左半区间
        ans = (ans + query(rt<<1,l,mid,x,y)) % p;
    if (y > mid)//若当前区间右端点大于mid,则肯定要查询右半区间
        ans = (ans + query(rt<<1|1,mid+1,r,x,y)) % p; 
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> T >> p;
    for(int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    Build(1,n,1);
    while(T--) {
        int a, l, r;
        cin >> a;
        if (a == 1) {
            int k;
            cin >> l >> r >> k;
            Update_section_mul(1, k, 1, n, l, r);
        } else if(a == 2) {
            int k;
            cin >> l >> r >> k;
            Update_section_add(1, k, 1, n, l, r);
        } else {
            cin >> l >> r;
            ll ans = query(1, 1, n, l, r);
            cout << ans << endl;
        }
    }
    return 0;
}

然后~恭喜 ac ~ 耶~!
在这里插入图片描述

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。