您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 1754 I Hate It：線段樹單點更新區間最大值模板

編輯：C++ 入門

題目與線段樹模板

HDU 1754：N 個學生分數（N ≤ 200,000），M 次操作：

Q a b：查詢區間 [a,b] 最大分數
U a b：將第 a 位學生分數更新為 b

標準線段樹維護區間最大值，單點更新、區間查詢均 O(log N)。

節點結構與核心函數

struct Node { int l, r, mx; } tree[MAXN*4];
int a[MAXN];

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

void update(int rt, int pos, int val) {
    if (tree[rt].l == tree[rt].r && tree[rt].l == pos) {
        tree[rt].mx = val; return;
    }
    if (pos <= tree[rt<<1].r) update(rt<<1, pos, val);
    else update(rt<<1|1, pos, val);
    tree[rt].mx = max(tree[rt<<1].mx, tree[rt<<1|1].mx);
}

int query(int rt, int l, int r) {
    if (l == tree[rt].l && r == tree[rt].r) return tree[rt].mx;
    if (r <= tree[rt<<1].r) return query(rt<<1, l, r);
    if (l >= tree[rt<<1|1].l) return query(rt<<1|1, l, r);
    return max(query(rt<<1, l, tree[rt<<1].r),
               query(rt<<1|1, tree[rt<<1|1].l, r));
}

完整 AC 程式碼

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
struct Node { int l, r, mx; } tree[MAXN*4];
int a[MAXN];

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

void update(int rt, int pos, int val) {
    if (tree[rt].l == tree[rt].r) { tree[rt].mx = val; return; }
    if (pos <= tree[rt<<1].r) update(rt<<1, pos, val);
    else update(rt<<1|1, pos, val);
    tree[rt].mx = max(tree[rt<<1].mx, tree[rt<<1|1].mx);
}

int query(int rt, int l, int r) {
    if (l == tree[rt].l && r == tree[rt].r) return tree[rt].mx;
    if (r <= tree[rt<<1].r) return query(rt<<1, l, r);
    if (l >= tree[rt<<1|1].l) return query(rt<<1|1, l, r);
    return max(query(rt<<1, l, tree[rt<<1].r),
               query(rt<<1|1, tree[rt<<1|1].l, r));
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        build(1, 1, n);
        char op[2];
        for (int i = 0; i < m; ++i) {
            scanf("%s", op);
            int x, y; scanf("%d%d", &x, &y);
            if (op[0] == 'Q') printf("%d\n", query(1, x, y));
            else update(1, x, y);
        }
    }
    return 0;
}