【模板】线段树

单点修改，区间最大

#include <cstdio>
#include <algorithm>
#define N 200010
#define INF 0x3f3f3f3f
#define DB printf("......\n")

using namespace std;

int a[N], tr[N << 2], ans;

void build(int l, int r, int id) {
    if (l == r) {
        tr[id] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, id << 1);
    build(mid + 1, r, id << 1 | 1);
    tr[id] = max(tr[id << 1], tr[id << 1 | 1]);
}

void update(int l, int r, int x, int v, int id) {
    tr[id] = max(tr[id], v);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) update(l, mid, x, v, id << 1);
    else update(mid + 1, r, x, v, id << 1 | 1);
}

void query(int l, int r, int ll, int rr, int id) {
    if (ll <= l && r <= rr) {
        ans = max(ans, tr[id]);
        return;
    }
    if (l > rr || r < ll) {
        return;
    }
    int mid = (l + r) >> 1;
    query(l, mid, ll, rr, id << 1);
    query(mid + 1, r, ll, rr, id << 1 | 1);
}

int main() {
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    build(1, n, 1);
    for (int i = 1; i <= m; ++i) {
        char ch = getchar();
        while (ch != 'U' && ch != 'Q') ch = getchar();
        if (ch == 'U') {
            int x, y;
            scanf("%d%d", &x, &y);
            update(1, n, x, y, 1);
        }
        if (ch == 'Q') {
            int x, y;
            scanf("%d%d", &x, &y);
            ans = 0;
            query(1, n, x, y, 1);
            printf("%d\n", ans);
        }
    }
    }
    return 0;
}

区间增加，区间求和

#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 100010;

int n, m, o, x, y;
LL s[N << 2], sign[N << 2], a[N << 2], k;

void pushdown (int rt, int ln, int rn){
    if (sign[rt]){
        sign[rt << 1] += sign[rt];
        sign[rt << 1 | 1] += sign[rt];
        s[rt << 1] += sign[rt] * ln;
        s[rt << 1 | 1] += sign[rt] * rn;
        sign[rt] = 0;
    }
}

void build_tree (int l, int r, int rt){
    if (l == r){
        s[rt] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build_tree (l, m, rt << 1);
    build_tree (m + 1, r, rt << 1 | 1);
    s[rt] = s[rt << 1] + s[rt << 1 | 1];
}

void update (int l, int r, int ll, int rr, int rt, LL p){
    if (l <= ll && rr <= r){
        s[rt] += p * (rr - ll + 1);
        sign[rt] += p;
        return;
    }
    int m = (ll + rr) >> 1;
    pushdown (rt, m - ll + 1, rr - m);
    if (l <= m) update (l, r, ll, m, rt << 1, p);
    if (r > m) update (l, r, m+1, rr, rt << 1 | 1, p);
    s[rt] = s[rt << 1] + s[rt << 1 | 1]; 
}

LL query (int l, int r, int ll, int rr, int rt){
    if (l <= ll && rr <= r){
        return s[rt];
    }
    int m = (ll + rr) >> 1;
    pushdown (rt, m - ll + 1, rr - m);
    LL ans = 0;
    if (l <= m) ans += query (l, r, ll, m, rt << 1);
    if (r > m) ans += query (l, r, m + 1, rr, rt << 1 | 1);
    return ans;
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n;++i){
        scanf("%lld", &a[i]);
    }
    build_tree (1, n, 1);
    for (int i = 1;i <= m;++i){
        char ch = getchar();
        while (ch != 'Q' && ch != 'C') ch = getchar();
        if (ch == 'C'){
            scanf("%d%d%lld", &x, &y, &k);
            update (x, y, 1, n, 1, k);
        }
        else{
            scanf("%d%d", &x, &y);
            printf("%lld\n", query (x, y, 1, n, 1));
        }
    }
    return 0;
}