# 合并排序樹以獲取范圍順序統計信息 > 原文： [https://www.geeksforgeeks.org/merge-sort-tree-for-range-order-statistics/](https://www.geeksforgeeks.org/merge-sort-tree-for-range-order-statistics/) 給定一個由`n`個數字組成的數組，任務是回答以下查詢： ``` kthSmallest(start, end, k) : Find the Kth smallest number in the range from array index 'start' to 'end'. ``` 例子： ``` Input : arr[] = {3, 2, 5, 1, 8, 9| Query 1: start = 2, end = 5, k = 2 Query 2: start = 1, end = 6, k = 4 Output : 2 5 Explanation: [2, 5, 1, 8] represents the range from 2 to 5 and 2 is the 2nd smallest number in the range[3, 2, 5, 1, 8, 9] represents the range from 1 to 6 and 5 is the 4th smallest number in the range ``` 關鍵思想是構建一個[分段樹](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/)，每個節點上都有一個向量，并且該向量按排序順序包含子范圍的所有元素。 而且，如果我們觀察到這種段樹結構，則該結構與[合并排序算法](https://www.geeksforgeeks.org/merge-sort/)期間形成的樹類似（這就是為什么將其稱為合并排序樹的原因） 我們使用與[合并排序樹（在給定行范圍內的較小或相等元素）](https://www.geeksforgeeks.org/merge-sort-tree-smaller-or-equal-elements-in-given-row-range/)中討論的相同的實現方式 首先，我們維護一個向量對，其中每個對`{value, index}`使得對的第一個元素代表輸入數組的元素，而對的第二個元素代表其出現的索引。 現在，我們基于每個對的第一個元素對對向量進行排序。 在此之后，我們將建立一個合并排序樹，其中每個節點都有一個在排序范圍內的索引向量。 當我們必須回答一個查詢時，我們發現第`K`個最小的數字是在左子樹中還是在右子樹中。 想法是使用兩個二分搜索并找到左側子樹中的元素數量，以使索引位于給定的查詢范圍內。 令此類索引的數量為`M`。 如果`M >= K`，則意味著我們將能夠在左側子樹中找到第`K`個最小的數字，因此我們在左側子樹中進行調用。 否則，第`K`個最小值位于右的子樹中，但是這次我們不必尋找第`K`個最小數量，因為我們已經有第`M`個最小的 HT 了。 左子樹中的范圍，因此我們應該在右子樹中尋找剩余部分，即第`KM`個。 這是第`K`個最小數字的索引，該索引處的值是所需的編號。 ``` // CPP program to implement k-th order statistics #include <bits/stdc++.h> using namespace std; const int MAX = 1000; // Constructs a segment tree and stores tree[] void buildTree(int treeIndex, int l, int r,? ???????vector<pair<int, int> > &a, vector<int> tree[]) { ????/* l => start of range, ????????r => ending of a range ????????treeIndex => index in the Segment Tree/Merge? ?????????????????????Sort Tree? */ ????/* leaf node */ ????if (l == r) { ????????tree[treeIndex].push_back(a[l].second); ????????return; ????} ????int mid = (l + r) / 2; ????/* building left subtree */ ????buildTree(2 * treeIndex, l, mid, a, tree); ????/* building left subtree */ ????buildTree(2 * treeIndex + 1, mid + 1, r, a, tree); ????/* merging left and right child in sorted order */ ????merge(tree[2 * treeIndex].begin(),? ??????????tree[2 * treeIndex].end(), ??????????tree[2 * treeIndex + 1].begin(),? ??????????tree[2 * treeIndex + 1].end(), ??????????back_inserter(tree[treeIndex])); } // Returns the Kth smallest number in query range int queryRec(int segmentStart, int segmentEnd,? ?????????????int queryStart, int queryEnd, int treeIndex, ?????????????????int K, vector<int> tree[]) { ????/* ????????segmentStart => start of a Segment, ????????segmentEnd?? => ending of a Segment, ????????queryStart?? => start of a query range, ????????queryEnd???? => ending of a query range, ????????treeIndex??? => index in the Segment? ????????????????????????Tree/Merge Sort Tree, ????????K? => kth smallest number to find? */ ????if (segmentStart == segmentEnd)? ????????return tree[treeIndex][0]; ????int mid = (segmentStart + segmentEnd) / 2; ????// finds the last index in the segment? ????// which is <= queryEnd ????int last_in_query_range =? ????????????(upper_bound(tree[2 * treeIndex].begin(), ??????????????????????????tree[2 * treeIndex].end(), ??????????????????????????????????????????queryEnd) ????????????????????- tree[2 * treeIndex].begin()); ????// finds the first index in the segment ????// which is >= queryStart ????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 >= K) { ????????// Kth smallest is in left subtree, ????????// so recursively call left subtree for Kth? ????????// smallest number ????????return queryRec(segmentStart, mid, queryStart,? ?????????????????????queryEnd, 2 * treeIndex, K, tree); ????} ????else { ????????// Kth smallest is in right subtree, ????????// so recursively call right subtree for the? ????????// (K-M)th smallest number ????????return queryRec(mid + 1, segmentEnd, queryStart, ???????????????queryEnd, 2 * treeIndex + 1, K - M, tree); ????} } // A wrapper over query() int query(int queryStart, int queryEnd, int K, int n, ??????????vector<pair<int, int> > &a, vector<int> tree[]) { ????return queryRec(0, n - 1, queryStart - 1, queryEnd - 1,? ???????????????????????????????????????????????1, K, tree); } // Driver code int main() { ????int arr[] = { 3, 2, 5, 1, 8, 9 }; ????int n = sizeof(arr)/sizeof(arr[0]); ????// vector of pairs of form {element, index} ????vector<pair<int, int> > v; ????for (int i = 0; i < n; i++) { ????????v.push_back(make_pair(arr[i], i)); ????} ????// sort the vector ????sort(v.begin(), v.end()); ????// Construct segment tree in tree[] ????vector<int> tree[MAX]; ????buildTree(1, 0, n - 1, v, tree); ????// Answer queries ????// kSmallestIndex hold the index of the kth smallest number ????int kSmallestIndex = query(2, 5, 2, n, v, tree); ????cout << arr[kSmallestIndex] << endl; ????kSmallestIndex = query(1, 6, 4, n, v, tree); ????cout << arr[kSmallestIndex] << endl; ????return 0; } ``` **輸出**： ``` 2 5 ``` 因此，通過在索引上建立合并排序樹，我們可以得到`L`到`R`范圍內的第`K`個最小數字的查詢，形式為 `O(n(logn)^2)`。 * * * * * *