天天看點
傳回

線段樹入門基礎題目集題解

1.​​HDU1166 敵兵布陣​​ 單點修+區間查詢+IO優化

題目要求單點修改，區間查詢。按照線段樹闆子打下來即可。注意IO優化，關閉緩沖流後不可混用​

​stdio​

​​和​

​iostream​

​​，否則WA的飛起。。

以及 注意開四倍空間。

#include <bits/stdc++.h>
using namespace std;

const int N = 50000 + 10;
int n, tree[N << 2], tt = 0;

inline void push_up(int rt){ tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; }

inline void build(int rt, int l, int r){
    if(l == r){
        cin >> tree[rt];
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    push_up(rt);
}

inline void update(int rt, int l, int r, int pos, int val){
    if(l == r){
        tree[rt] += val;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(rt << 1, l, mid, pos, val);
    else update(rt << 1 | 1, mid + 1, r, pos, val);
    push_up(rt);
}

inline int query(int rt, int l, int r, int L, int R){
    if(l >= L && r <= R) return tree[rt];
    int mid = l + r >> 1, ans = 0;
    if(mid >= L) ans += query(rt << 1, l, mid, L, R);
    if(mid < R) ans += query(rt << 1 | 1, mid + 1, r, L, R);
    return ans;
}

inline void solve(){
    cin >> n;
    build(1, 1, n);
    cout << "Case " << ++tt << ":" << endl;
    //printf("%d:\n", ++tt);
    char strr[10];
    while(cin >> strr){
        if(!strcmp(strr, "End")) break;
        else if(!strcmp(strr, "Add")){
            int a, b; cin >> a >> b;
            update(1, 1, n, a, b);
        }
        else if(!strcmp(strr, "Sub")){
            int a, b; cin >> a >> b;
            update(1, 1, n, a, -b);
        }
        else{
            int a, b; cin >> a >> b;
            int ans = query(1, 1, n, a, b);
            cout << ans << endl;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

2.​​HDU1754 I Hate It​​ 單點修改+區間查詢+維護區間最小值+IO優化

線段樹模闆題，維護區間最小值+單點修改無标記，一路打下來就可以，注意空間限制比較大，建樹直接讀資料，不要單獨存。

資料量不小，考慮IO優化。

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 10;

int n, m, tree[N << 2];

inline int read() {
    int f = 1, x = 0; char s = getchar(); 
    while(s < '0'||s > '9'){ if(s =='-') f = -1; s = getchar(); } 
    while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
    return x *= f; 
}

inline void push_up(int rt){ tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]); }

void build(int rt, int l, int r){
    if(l == r){
        tree[rt] = read();
        return;
    }
    int mid = l + r >> 1; 
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    push_up(rt);
}

void update(int rt, int l, int r, int pos, int val){
    if(l == r){
        tree[rt] = val;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(rt << 1, l, mid, pos, val);
    else update(rt << 1 | 1, mid + 1, r, pos, val);
    push_up(rt);
}

int query(int rt, int l, int r, int L, int R){
    if(l >= L && r <= R) return tree[rt];
    int ans = -1, mid = l + r >> 1;
    if(mid >= L) ans = max(ans, query(rt << 1, l, mid, L, R));
    if(mid < R) ans = max(ans, query(rt << 1 | 1, mid + 1, r, L, R));
    return ans;
}

inline void solve(){
    //for(int i = 0; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(m--){
        char op; scanf("%c", &op);
        if(op == 'Q'){
            int aa = read(), b = read();
            cout << query(1, 1, n, aa, b) << endl;
        }
        else{
            int aa = read(), b = read();
            //a[aa] = b;
            update(1, 1, n, aa, b);
        }
    }
}

signed main(){
    while(~scanf("%d%d", &n, &m)) solve();
    return 0;
}

3.​​HDU1689 Just a Hook​​ 區間修改+Lazy标記+根節點查詢

Problem Description

題目大意： 預設區間的每一個數的權值為1，不斷的修改區間的某一範圍，求最終的區間權值和

思路： 線段樹區間更新。但是不能修改到底，資料範圍限制導緻徹底修改會逾時，是以需要打标記，注意這裡标記不存倍數、加數，而是修改之後的值。每次更新到點的時候下放即可。

關于标記這裡不展開叙述，具體見OIWIKI。

Accepted Code

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    int f = 1, x = 0; char s = getchar(); 
    while(s < '0'||s > '9'){ if(s == '-') f = -1; s = getchar(); } 
    while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
    return x *= f; 
}

const int N = 1e5 + 10;

int n, q, k = 0, tree[N << 2], lazy[N << 2];

inline void push_up(int rt){ tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; }

inline void push_down(int rt, int m){
    if(lazy[rt]){
        lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
        tree[rt << 1] = lazy[rt] * (m - (m >> 1));
        tree[rt << 1 | 1] = lazy[rt] * (m >> 1);
        lazy[rt] = 0;
    }
}

void build(int rt, int l, int r){
    if(l == r){
        tree[rt] = 1;
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    lazy[rt] = 0; 
    push_up(rt);
}

void update(int rt, int l, int r, int L, int R, int val){
    if(l >= L && r <= R){
        lazy[rt] = val;
        tree[rt] = val * (r - l + 1);
        return;
    }
    push_down(rt, r - l + 1);
    int mid = (l + r) >> 1;
    if(mid >= L) update(rt << 1, l, mid, L, R, val);
    if(mid < R) update(rt << 1 | 1, mid + 1, r, L, R, val);
    push_up(rt);
}


inline void solve(){
    n = read(), q = read();
    build(1, 1, n);
    while(q--){
        int a = read(), b = read(), c = read();
        update(1, 1, n, a, b, c);
    }
    printf("Case %d: The total value of the hook is %d.\n", ++k, tree[1]);
}

signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
}

4.​​POJ3468 A Simple Problem with Integers​​ 維護區間和+區間修改+Lazy标記+區間查詢 

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, q, tree[N << 2], lazy[N << 2];

inline int read() {
    int f = 1, x = 0; char s = getchar(); 
    while(s < '0'||s > '9'){ if(s =='-') f = -1; s = getchar(); } 
    while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
    return x *= f; 
}

inline void push_up(int rt){ tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; }

inline void push_down(int rt, int m){
    if(lazy[rt]){
        lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
        tree[rt << 1] += lazy[rt] * (m - (m >> 1));
        tree[rt << 1 | 1] += lazy[rt] * (m >> 1);
        lazy[rt] = 0;
    }
}

void build(int rt, int l, int r){
    lazy[rt] = 0;
    if(l == r){
        tree[rt] = read();
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    push_up(rt);
}

void update(int rt, int l, int r, int L, int R, int val){
    if(l >= L && r <= R){
        lazy[rt] += val;
        tree[rt] += (r - l + 1) * val;
        return;
    }
    int mid = l + r >> 1;
    push_down(rt, r - l + 1);
    if(mid >= L) update(rt << 1, l, mid, L, R, val);
    if(mid < R) update(rt << 1 | 1, mid + 1, r, L, R, val);
    push_up(rt);
}

int query(int rt, int l, int r, int L, int R){
    if(l >= L && r <= R) return tree[rt];
    int mid = l + r >> 1, ans = 0;
    push_down(rt, r - l + 1);
    if(mid >= L) ans += query(rt << 1, l, mid, L, R);
    if(mid < R) ans += query(rt << 1 | 1, mid + 1, r, L, R);
    return ans;
}

inline void solve(){
    build(1, 1, n);
    while(q--){
        char op[2]; scanf("%s", op);
        if(op[0] == 'Q'){
            int a = read(), b = read();
            cout << query(1, 1, n, a, b) << endl;
        }
        else{
            int a = read(), b = read(), c = read();
            update(1, 1, n, a, b, c);
        }
    }
}

signed main(){
    while(~scanf("%d%d", &n, &q)) solve();
    return 0;
}
資料結構 算法 ACM競賽 #include 區間查詢
上一篇: 阿裡巴巴開放平台php元件,阿裡巴巴開放平台
下一篇: C/C++ 筆記（1）-- malloc 的工作原理

繼續閱讀