Truy vấn Min-Max trên mảng (Range Queries) trong C++

Cho mảng Arr[] N phần tử. Tìm giá trị nhỏ nhất và lớn nhất trong khoảng chỉ số từ QStart đến QEnd.

Ví dụ

Đầu vào: Arr[] = {1, 2, 3, 4, 5}, QStart = 1, QEnd = 4

Đầu ra: Min = 2, Max = 5

Đầu vào: Arr[] = {10, 12, 3, 2, 5, 18}, QStart = 2, QEnd = 5

Đầu ra: Min = 2, Max = 18

Phương pháp: Segment Tree (Cây đoạn)

• Xây dựng Segment Tree lưu trữ (minVal, maxVal) cho mỗi đoạn.
• Truy vấn: nếu đoạn truy vấn bao phủ hoàn toàn nút → trả về giá trị nút. Nếu ngoài phạm vi → trả về giá trị vô cực. Nếu giao nhau → đệ quy con trái/phải và gộp kết quả.
• Độ phức tạp: Xây dựng O(N), Truy vấn O(log N).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

struct Value {
    int minVal;
    int maxVal;
};

Value minmaxFind(Value *root, int startT, int endT, int qStart, int qEnd, int pos) {
    Value temp, lpos, rpos;
    if (qStart <= startT && qEnd >= endT) return root[pos];
    if (endT < qStart || startT > qEnd) {
        temp.minVal = INT_MAX; temp.maxVal = INT_MIN; return temp;
    }
    int mid = startT + (endT - startT) / 2;
    int p1 = 2*pos+1, p2 = 2*pos+2;
    lpos = minmaxFind(root, startT, mid, qStart, qEnd, p1);
    rpos = minmaxFind(root, mid+1, endT, qStart, qEnd, p2);
    temp.minVal = min(lpos.minVal, rpos.minVal);
    temp.maxVal = max(lpos.maxVal, rpos.maxVal);
    return temp;
}

Value minMax(Value *root1, int num, int qStart1, int qEnd1) {
    Value temp1;
    if (qStart1 < 0 || qEnd1 > num-1 || qStart1 > qEnd1) {
        cout << "Invalid query range!";
        temp1.minVal = INT_MAX; temp1.maxVal = INT_MIN; return temp1;
    }
    return minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0);
}

void segmentTree(int arr2[], int startT2, int endT2, Value *root2, int pos2) {
    if (startT2 == endT2) {
        root2[pos2].minVal = root2[pos2].maxVal = arr2[startT2];
        return;
    }
    int p1 = pos2*2+1, p2 = pos2*2+2;
    int mid = startT2 + (endT2 - startT2)/2;
    segmentTree(arr2, startT2, mid, root2, p1);
    segmentTree(arr2, mid+1, endT2, root2, p2);
    root2[pos2].minVal = min(root2[p1].minVal, root2[p2].minVal);
    root2[pos2].maxVal = max(root2[p1].maxVal, root2[p2].maxVal);
}

Value* createTree(int arr0[], int num0) {
    int height = ceil(log2(num0));
    int maxS = 2 * (int)pow(2, height) - 1;
    Value *root0 = new Value[maxS];
    segmentTree(arr0, 0, num0-1, root0, 0);
    return root0;
}

int main() {
    int Arr[] = {1, 2, 3, 4, 5};
    int length = sizeof(Arr)/sizeof(Arr[0]);
    Value *tree = createTree(Arr, length);
    int QStart = 1, QEnd = 4;
    Value ans = minMax(tree, length, QStart, QEnd);
    cout << "Minimum Value: " << ans.minVal << "\nMaximum Value: " << ans.maxVal;
    return 0;
}

Đầu ra chương trình

Minimum Value: 2
Maximum Value: 5