线段树整理

区间最大值

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> 
#include <queue>
#define re register
#define lson o<<1
#define rson o<<1|1
using namespace std ;
const int maxn = 200005 ;

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

int n , m , a , b ;
int tree[maxn * 4] ;

inline void pushup(int o) {
    tree[o] = max(tree[lson] , tree[rson]) ;
}

inline void build(int o , int l , int r) {
    if(l == r) {
        tree[o] = read() ;
        return ;
    }
    int mid = (l + r) / 2 ;
    build(lson , l , mid) ;
    build(rson , mid + 1 , r) ;
    pushup(o) ;
}

inline int query(int o , int l , int r , int x , int y) {
    if(x <= l && r <= y) 
        return tree[o] ;
    int maxx = 0 ;
    int mid = (l + r) / 2 ;
    if(x <= mid)  maxx = max(maxx , query(lson , l , mid , x , y)) ;
    if(y > mid)  maxx = max(maxx , query(rson , mid + 1 , r , x , y)) ;
    return maxx ;
}

inline void update(int o , int l , int r , int x , int y) {
    if(l == r) {
        tree[o] = y ;
        return ;
    }
    int mid = (l + r) / 2 ;
    if(x <= mid)  update(lson , l , mid , x , y) ;
    else update(rson , mid + 1 , r , x , y) ;
    pushup(o) ;
}

int main () {
    freopen("hate it.in" , "r" , stdin) ;
    n = read () ; m = read () ;
    build(1 , 1 , n) ;
    char flag ;
    while(m--) {
        cin >> flag ;
        if(flag == 'Q') {
            a = read (); b = read () ;
            printf("%d\n" , query(1 , 1 , n , a , b)) ;
        }
        else {
            a = read () ;  b = read () ;
            update(1 , 1 , n , a , b) ;
        }
    }
    return 0 ;
}

例题：洛古P1531 I Hate it

区间最小值

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define re register
using namespace std ;
const int maxm = 300005 ;

#define lson o<<1
#define rson o<<1|1

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

int m , n , a , b ;
int tree[maxm] ;

inline void pushup(int o) {
    tree[o] = min(tree[lson] , tree[rson]) ;
}

inline void build(int o , int l , int r) {
    if(l == r) {
        tree[o] = read() ;
        return ;
    }
    int mid = (l + r) / 2 ;
    build(lson , l , mid) ;
    build(rson , mid + 1 , r) ;
    pushup(o) ;
}

inline int query(int o , int l , int r , int x , int y) {
    if(x <= l && r <= y)
        return tree[o] ;
    int minn = 1e9 ;
    int mid = (l + r) / 2;
    if(x <= mid) minn = min(minn, query(lson , l , mid , x , y)) ;
    if(y > mid) minn = min(minn, query(rson , mid + 1 , r , x , y)) ;
    return minn;
}

inline void update(int o , int l , int r , int x , int y) {
    if(l == r) {
        tree[o] = max(tree[o] , y) ;
        return ;
    }
    int mid = (l + r) / 2 ;
    if(x <= mid)  update(lson , l , mid , x , y) ;
    else update(rson , mid + 1 , r , x , y) ;
    pushup(o) ;
}

int main () {
    m = read () ; n = read () ;
    build(1 , 1 , m) ;
    char flag ;
    while(n --) {
        cin >> flag ;
        if(flag == 'Q') {
            a = read (); b = read () ;
            printf("%d\n" , query(1 , 1 , m , a , b)) ;
        }
        else {
            a = read () ;  b = read () ;
            update(1 , 1 , m , a , b) ;
        }
    }
    return 0 ;
}

例题：洛古P1816 忠诚

区间求和

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> 
#include <queue>
#define re register
#define lson o<<1
#define rson o<<1|1
#define ll long long
using namespace std ;
const int maxn = 100005 ;

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

long long n , m , x , y , k ;
long long tree[maxn * 4] , add[maxn * 4] ;
long long flag ;

inline void pushup(ll o) {
    tree[o] = tree[lson] + tree[rson] ;
}

inline void pushdown(ll o , ll l , ll r) {
    if(add[o]) {
        ll mid = (l + r) / 2 ;
        add[lson] += add[o] ;
        add[rson] += add[o] ;
        tree[lson] += (mid - l + 1) * add[o] ;
        tree[rson] += (r - mid) * add[o] ;
        add[o] = 0 ;
    }
} 

inline void build(ll o , ll l , ll r) {
    if(l == r) {
        tree[o] = read() ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(lson , l , mid) ;
    build(rson , mid + 1 , r) ;
    pushup(o) ;
}

inline void update(ll o , ll l , ll r , ll x , ll y , ll val) {
    if(x <= l && r <= y) {
        tree[o] +=(r - l + 1) * val ;
        add[o] += val ;
        return ;
    }
    pushdown(o , l , r) ;
    ll mid = (l + r) / 2 ;
    if(x <= mid)  update(lson , l , mid , x , y , val) ;
    if(y > mid) update(rson , mid + 1 , r , x , y , val) ;
    pushup(o) ;
}

inline ll query(ll o , ll l , ll r , ll x , ll y) {
    if(x <= l && r <= y) {
        return tree[o] ;
    }
    pushdown(o , l , r) ;
    int mid = (l + r) / 2 ;
    ll ans = 0 ;
    if(x <= mid) ans += query(lson , l , mid , x , y) ;
    if(y > mid)  ans += query(rson , mid + 1 , r , x , y) ;
    return ans ;
}

int main() {
    n = read() ; m = read() ;
    build(1 , 1 , n) ;
    while(m--) {
        flag = read() ;
        if(flag == 1) {
            x = read() ; y = read() ; k = read () ;
            update(1 , 1 , n , x , y , k) ;
        }
        else {
            x = read () ; y = read () ;
            printf("%lld\n" , query(1 , 1 , n , x , y)) ;
        }
    }
    return 0 ;
}

线段树整理

原文：https://www.cnblogs.com/Stephen-F/p/10805470.html