POJ 3264：平衡隊列——區間最值查詢（RMQ）

題目描述

N 條牛（N ≤ 50,000）固定排序，Q 次查詢（Q ≤ 200,000），每次詢問區間 [A, B] 內最高牛與最矮牛的高度差。

解法對比

線段樹實現（本文採用）

每個節點存儲區間最大值 t 和最小值 s。查詢時合併子區間極值。

C++ 代碼

#include <cstdio>
#include <climits>
#define MAX 50100

struct Node { int mx, mn; } st[MAX*4];
int a[MAX];

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

void query(int L, int R, int l, int r, int p, int& mx, int& mn) {
    if (L <= l && r <= R) {
        mx = max(mx, st[p].mx);
        mn = min(mn, st[p].mn);
        return;
    }
    int mid = (l+r)>>1;
    if (R <= mid) query(L, R, l, mid, p<<1, mx, mn);
    else if (L > mid) query(L, R, mid+1, r, p<<1|1, mx, mn);
    else {
        query(L, R, l, mid, p<<1, mx, mn);
        query(L, R, mid+1, r, p<<1|1, mx, mn);
    }
}

int main() {
    int n, q; scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, n, 1);
    while (q--) {
        int a, b; scanf("%d%d", &a, &b);
        int mx = INT_MIN, mn = INT_MAX;
        query(a, b, 1, n, 1, mx, mn);
        printf("%d\n", mx - mn);
    }
    return 0;
}

ST 算法優化提示

// 預處理 log 表
log2[1] = 0;
for (int i = 2; i <= N; ++i) log2[i] = log2[i>>1] + 1;

// 構建稀疏表
for (int i = 1; i <= n; ++i) st[i][0].mx = st[i][0].mn = a[i];
for (int j = 1; (1<

複雜度

線段樹：預處理 O(N)，查詢 O(log N)，總約 1.5s
ST 算法：預處理 O(N log N)，查詢 O(1)，總 < 0.5s