Merge Sort Tree ใน C++

เราได้รับอาร์เรย์จำนวนเต็ม ชุดของตัวชี้เริ่มต้นและจุดสิ้นสุดของ Segment และค่า Key และข้อความปัญหาคือการหาค่าทั้งหมดในช่วงที่กำหนดซึ่งน้อยกว่าหรือเท่ากับค่า Key ที่กำหนด

เข้าใจด้วยตัวอย่าง

Input - arr[] = {7, 8, 1, 4, 6, 8, 10}

Segment 1: start = 2, end = 4, k = 2

Segment 2: start = 1, end = 6, k = 3

Output - จำนวนที่น้อยกว่าหรือเท่ากับค่า Key ในช่วงที่กำหนดคือ 2, 6

คำอธิบาย - [8, 1, 4] แทนช่วงจาก 2 ถึง 4 และ 2 คือตัวเลขที่เล็กที่สุดลำดับที่ 2 ในช่วง [7, 8, 1, 4, 6, 8] แทนช่วงจาก 1 ถึง 6 และ 6 คือตัวเลขที่เล็กที่สุดลำดับที่ 3 ในช่วง

Input - arr[] = {2, 7, 9, 4, 6, 5, 1}

Segment 1: start = 3, end = 6, k = 4

Segment 2: start = 2, end = 5, k = 3

Output - จำนวนที่น้อยกว่าหรือเท่ากับค่า Key ในช่วงที่กำหนดคือ: 9, 7

คำอธิบาย - [9, 4, 6, 5] แทนช่วงจาก 3 ถึง 6 และ 9 คือตัวเลขที่เล็กที่สุดลำดับที่ 4 ในช่วงที่กำหนด [7, 9, 4, 6] แทนช่วงจาก 2 ถึง 4 และ 7 คือตัวเลขที่เล็กที่สุดลำดับที่ 3 ในช่วง Segment ที่กำหนด

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• ประกาศอาร์เรย์แบบจำนวนเต็ม คำนวณขนาดของอาร์เรย์ ประกาศตัวแปร vector แบบ pair ของจำนวนเต็ม เริ่มลูป FOR เพื่อ push ข้อมูลจากอาร์เรย์ไปยัง vector

• จัดเรียง (Sort) vector ที่กำหนด สร้าง vector array แบบจำนวนเต็มด้วยขนาด MAX

• เรียกฟังก์ชัน generateTree(1, 0, size-1, vec, tree) และตั้งค่า getSmallestIndex เป็น queryWrapper(2, 5, 2, size, vec, tree)

• พิมพ์ input[getSmallestIndex]

• ตั้งค่า getSmallestIndex เป็นการเรียกฟังก์ชัน queryWrapper(1, 6, 4, size, vec, tree)

• ภายในฟังก์ชัน void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int>> &a, vector<int> tree[])

  • ตรวจสอบ IF leftIndex เท่ากับ rightIndex แล้วตั้งค่า tree[treeIndex].push_back(a[leftIndex].second) และ return

  • ตั้งค่า midValue เป็น (leftIndex+rightIndex)/2 และเรียก generateTree(2*treeIndex, leftIndex, midValue, a, tree), generateTree(2*treeIndex+1, midValue+1, rightIndex, a, tree) และ merge(tree[2*treeIndex].begin(), tree[2*treeIndex].end(), tree[2*treeIndex+1].begin(), tree[2*treeIndex+1].end(), back_inserter(tree[treeIndex]))

• ภายในฟังก์ชัน int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector<int> tree[])

  • ตรวจสอบ IF startIndex เท่ากับ endIndex แล้วคืนค่า tree[treeIndex][0]

  • ตั้งค่า mid เป็น (startIndex+endIndex)/2, last_in_query_range เป็น (upper_bound(...) - tree[2*treeIndex].begin())

  • ตั้งค่า first_in_query_range เป็น (lower_bound(...) - tree[2*treeIndex].begin()) และ M เป็น last_in_query_range - first_in_query_range

  • ตรวจสอบ IF M มากกว่าหรือเท่ากับ key แล้วคืนค่า calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2*treeIndex, key, tree)

  • ELSE คืนค่า calculateKSmallest(mid+1, endIndex, queryStart, queryEnd, 2*treeIndex+1, key-M, tree)

• ภายในฟังก์ชัน int queryWrapper(int queryStart, int queryEnd, int key, int n, vector<pair<int, int>> &a, vector<int> tree[])

  • คืนค่าการเรียกฟังก์ชัน calculateKSmallest(0, n-1, queryStart-1, queryEnd-1, 1, key, tree)

ตัวอย่างโค้ด

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

const int MAX = 1000;

void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int>> &a, vector<int> tree[]) {
    if (leftIndex == rightIndex) {
        tree[treeIndex].push_back(a[leftIndex].second);
        return;
    }
    int midValue = (leftIndex + rightIndex) / 2;
    generateTree(2 * treeIndex, leftIndex, midValue, a, tree);
    generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree);
    merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(), 
          tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex]));
}

int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector<int> tree[]) {
    if (startIndex == endIndex) {
        return tree[treeIndex][0];
    }
    int mid = (startIndex + endIndex) / 2;
    int last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin());
    int first_in_query_range = (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin());
    int M = last_in_query_range - first_in_query_range;
    if (M >= key) {
        return calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree);
    } else {
        return calculateKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree);
    }
}

int queryWrapper(int queryStart, int queryEnd, int key, int n, vector<pair<int, int>> &a, vector<int> tree[]) {
    return calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, 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(make_pair(input[i], i));
    }
    sort(vec.begin(), vec.end());
    vector<int> tree[MAX];
    generateTree(1, 0, size - 1, vec, tree);
    cout<<"Count of number which are smaller than or equal to key value in the given range are:"<<endl;
    int getSmallestIndex = queryWrapper(2, 4, 2, size, vec, tree);
    cout << input[getSmallestIndex] << endl;
    getSmallestIndex = queryWrapper(1, 6, 3, size, vec, tree);
    cout << input[getSmallestIndex] << endl;
    return 0;
}

ผลลัพธ์

หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้:

Count of number which are smaller than or equal to key value in the given range are: 4 6