RMQ問題——線段樹

上篇說到 RMQ 問題可以用 ST 表算法處理，但需要在線修改的時候，線段樹是更好的選擇。
如圖，很明顯線段樹是個二叉搜索樹
在這裡插入圖片描述
要注意的點如下：

線段樹用數組存儲，數組空間簡單的就一般開到原數組的 4*n 倍（準確的說是將 n 向上擴充到 2 的幂次方然後乘 2，如 5->8->16）
線段樹數組存儲中，某個結點的編號為 n，則其左子結點編號為 2 * n（表示成 n << 1），右子節點編號為 2*n+1 (表示為 n << 1 | 1)
規定根節點為 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
    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;
}

二、區間修改（和、差、積、商等）#

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 ~ 耶～！
在這裡插入圖片描述