線段樹 (Segment Tree)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

int arr[500001], N;
int nodes[2000001]; // 每個節點都儲存自己區間的答案，並且節點號碼從 1 開始，才能遵循 LeftChild: 2 倍、RightChild: 2 倍 + 1 原則
inline int left(int p) { return p << 1; }
inline int right(int p) { return left(p) + 1; }
int build(int p, int l, int r) { // 求出區間 [l-r] 的答案並儲存進號碼 p 的節點
    // assert(l <= r); // 從中間剖分的過程中，左索引值不可能超過右索引值
    if (l == r) return nodes[p] = arr[l]; // 區間為單點元素時只得自行計算出答案
    int m = (l + r) >> 1; // 取中點
    auto a1 = build(left(p), l, m); // 求出區間 [l-m] 的答案並儲存進號碼 2p 的節點
    auto a2 = build(right(p), m+1, r); // 求出區間 [(m+1)-r] 的答案並儲存進號碼 2p + 1 的節點
    return nodes[p] = max(a1, a2); // 合併左右子樹的兩個答案以求出自己的答案，並存進節點中
}
int L, R; // 用於 recursive 和 query，表示欲查詢區間為 [L-R]
int recursive(int p, int l, int r) { // assert(l <= r); // 給定過程中已經有答案的節點區間 [l-r]，最後會回傳此區間和欲查詢區間 [L-R] 交集之後的答案，注意這三個數字本應與 build 過程中所設定的一致
    if (r < L || R < l) return -INT_MAX; // 如果節點區間與欲查詢區間沒有重疊，則希望此答案為單位元素 (做運算之後不影響其他區間的答案)
    if (L <= l && r <= R) return nodes[p]; // 如果節點區間已經被完整包覆在欲查詢區間之內，則直接貢獻答案 (停止繼續遞迴)
    // 如果節點區間和欲查詢區間僅部分重疊，則把自己這個節點區間再切成兩半，分別繼續做 recursive
    int m = (l + r) >> 1; // 取中點，注意到下面的 left(p), l, m 和 right(p), m+1, r 的 pattern 會與 build 的過程完全相同
    return max(recursive(left(p), l, m), recursive(right(p), m+1, r));
}
int query(int l, int r) {
    L = l; R = r; // assert(L <= R); // 欲查詢區間 [L-R] 在計算過程中不會改變
    return recursive(1, 1, N); // 給定大區間 [1-N] 內所有子區間的已知資料，如何求出恰為 [L-R] 區間的答案？
}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    cin >> N;
    for (int i=1; i<=N; i++) cin >> arr[i];
    build(1, 1, N);
    int M; cin >> M;
    for (int i=0; i<M; i++) {
        int a, b; cin >> a >> b;
        if (a > b) swap(a, b);
        cout << query(a, b) << endl;
    }
    return 0;
}