Merge Sort Tree trong C++

Merge Sort Tree là cấu trúc dữ liệu kết hợp Segment Tree và Merge Sort. Mỗi nút của Segment Tree lưu một mảng đã sắp xếp của đoạn tương ứng. Hỗ trợ truy vấn: tìm phần tử thứ K nhỏ nhất trong đoạn [L, R] hoặc đếm số phần tử ≤ K trong đoạn.

Ví dụ

Input: arr[] = {7, 8, 1, 4, 6, 8, 10}
Query 1: L=2, R=4, k=2 → Output: 4 (phần tử thứ 2 nhỏ nhất trong [8,1,4] là 4)
Query 2: L=1, R=6, k=3 → Output: 6 (phần tử thứ 3 nhỏ nhất trong [7,8,1,4,6,8] là 6)

Cấu trúc

• Xây dựng: đệ quy chia đoạn, gộp 2 mảng con đã sort bằng std::merge.
• Truy vấn: tại mỗi nút, dùng upper_bound/lower_bound đếm số phần tử trong khoảng truy vấn. Nếu số lượng ≥ K, đi nhánh trái; ngược lại đi nhánh phải với K trừ đi số lượng nhánh trái.

Mã nguồn C++

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

const int MAX = 1000;

void buildTree(int node, int l, int r, vector<pair<int,int>> &a, vector<int> tree[]) {
    if (l == r) {
        tree[node].push_back(a[l].second);
        return;
    }
    int mid = (l + r) / 2;
    buildTree(2*node, l, mid, a, tree);
    buildTree(2*node+1, mid+1, r, a, tree);
    merge(tree[2*node].begin(), tree[2*node].end(),
          tree[2*node+1].begin(), tree[2*node+1].end(),
          back_inserter(tree[node]));
}

int queryKth(int node, int l, int r, int ql, int qr, int k, vector<int> tree[]) {
    if (l == r) return tree[node][0];
    int mid = (l + r) / 2;
    int leftCount = upper_bound(tree[2*node].begin(), tree[2*node].end(), qr) - lower_bound(tree[2*node].begin(), tree[2*node].end(), ql);
    if (leftCount >= k)
        return queryKth(2*node, l, mid, ql, qr, k, tree);
    else
        return queryKth(2*node+1, mid+1, r, ql, qr, k - leftCount, tree);
}

int queryWrapper(int ql, int qr, int k, int n, vector<pair<int,int>> &a, vector<int> tree[]) {
    return queryKth(0, n-1, ql-1, qr-1, 1, k, tree);
}

int main() {
    int input[] = {7, 8, 1, 4, 6, 8, 10};
    int size = sizeof(input) / sizeof(input[0]);
    vector<pair<int,int>> vec;
    for (int i = 0; i < size; i++) vec.push_back({input[i], i});
    sort(vec.begin(), vec.end());

    vector<int> tree[MAX];
    buildTree(1, 0, size-1, vec, tree);

    cout << "Kết quả truy vấn: " << endl;
    int idx = queryWrapper(2, 4, 2, size, vec, tree);
    cout << input[idx] << endl;
    idx = queryWrapper(1, 6, 3, size, vec, tree);
    cout << input[idx] << endl;
    return 0;
}

Kết quả

Kết quả truy vấn: 4 6

Giải thích

Mảng vec lưu {giá trị, chỉ số gốc} và sort theo giá trị. Segment Tree lưu chỉ số gốc theo thứ tự giá trị. Truy vấn dùng binary search trên mảng đã sort của mỗi nút để đếm số phần tử rơi trong khoảng chỉ số [ql, qr].

Kết luận

Merge Sort Tree cho phép truy vấn thống kê thứ tự (k-th smallest, count ≤ x) trên đoạn trong O(log²N). Mã C++ sử dụng vector, merge, upper_bound/lower_bound. Cấu trúc này rất mạnh trong lập trình thi đấu.