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

問題

序列長度 N，M 次操作：

• U a b：位置 a 更新為 b
• Q a b：查詢區間 [a,b] 最大值

線段樹結構

• 節點存儲區間最大值
• 建樹 O(N)，遞歸分治
• 單點更新 O(log N)，自底向上維護
• 區間查詢 O(log N)，標準分治

完整模板

const int MAXN = 200000;
int tree[MAXN*4];

void build(int node, int l, int r) {
    if (l == r) { scanf("%d", &tree[node]); return; }
    int mid = (l+r)/2;
    build(node*2, l, mid);
    build(node*2+1, mid+1, r);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

void update(int node, int l, int r, int pos, int val) {
    if (l == r) { tree[node] = val; return; }
    int mid = (l+r)/2;
    if (pos <= mid) update(node*2, l, mid, pos, val);
    else update(node*2+1, mid+1, r, pos, val);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

int query(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[node];
    int mid = (l+r)/2;
    if (qr <= mid) return query(node*2, l, mid, ql, qr);
    if (ql > mid) return query(node*2+1, mid+1, r, ql, qr);
    return max(query(node*2, l, mid, ql, mid),
               query(node*2+1, mid+1, r, mid+1, qr));
}

主程序

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        build(1, 1, n);
        char op[2];
        while (m--) {
            scanf("%s", op);
            int a, b; scanf("%d%d", &a, &b);
            if (op[0] == 'U') update(1, 1, n, a, b);
            else printf("%d\n", query(1, 1, n, a, b));
        }
    }
}

注意：HDU 1754 多組測試用例，需在循環中重新建樹。