C++中的合并排序树
给定一个整数数组，一组段开始和结束指针以及一个键值，这里的问题陈述是找到给定范围内小于或等于给定键值的所有值。
让我们用例子来理解
输入 -arr[]={7,8,1,4,6,8,10}
第1段：开始=2，结束=4，k=2
第2段：开始=1，结束=6，k=3
输出 -给定范围内小于或等于键值的数字计数为26
说明 -[8,1,4]表示从2到4的范围，2是范围内第二小的数字[7,8,1,4,6,8]表示从1到6的范围，6是范围内第三小的数字
输入 -arr[]={2,7,9,4,6,5,1|
第1段：开始=3，结束=6，k=4
第2段：开始=2，结束=5，k=3
输出 -小于或等于给定范围内的键值的数字计数为：97
说明 -[9,4,6,5]表示从3到6的范围，9是给定范围内的第4个最小数字[7,9,4,6]表示从2到4的范围，7是第三个给定段范围内的最小数字
以下程序中使用的方法如下-
声明一个整型数组。计算数组的大小。声明一个形成整数类型对的向量类型变量。启动FOR循环将数据从数组推送到向量。
对给定的向量进行排序。创建一个大小为MAX的整数类型的向量数组。
将该函数调用为generateTree(1,0,size-1,vec,tree)并将getSmallestIndex设置为queryWrapper(2,5,2,size,vec,tree)。
打印输入[getSmallestIndex]。
设置getSmallestIndex以将函数调用为queryWrapper(1,6,4,size,vec,tree)。
在函数内部作为voidgenerateTree(inttreeIndex,intleftIndex,intrightIndex,vector<pair<int,int>>&a,vector<int>tree[])
检查IFleftIndex到rightIndex然后设置tree[treeIndex].push_back(a[leftIndex].second)并返回
将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()..settree[2*treeIndex+1].end(),back_inserter(tree[treeIndex]))
在函数内部作为intcalculateKSmallest(intstartIndex,intendIndex,intqueryStart,intqueryEnd,inttreeIndex,intkey,vectortree[])
检查IFstartIndex到endIndex然后返回tree[treeIndex][0]
将mid设置为(startIndex+endIndex)/2，将last_in_query_range设置为(upper_bound(tree[2*treeIndex].begin(),tree[2*treeIndex].end(),queryEnd)-tree[2*treeIndex].begin())
将first_in_query_range设置为(lower_bound(tree[2*treeIndex].begin(),tree[2*treeIndex].end(),queryStart)-tree[2*treeIndex].begin())并将M设置为last_in_query_range-first_in_query_range
检查IFM大于等于key然后返回calculateKSmallest(startIndex,mid,queryStart,queryEnd,2*treeIndex,key,tree)
ELSE，然后返回calculateKSmallest(mid+1,endIndex,queryStart,queryEnd,2*treeIndex+1,key-M,tree)。
在函数内部intqueryWrapper(intqueryStart,intqueryEnd,intkey,intn,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<<"给定范围内小于或等于键值的数字计数为："<<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;
}输出结果如果我们运行上面的代码，它将生成以下输出
给定范围内小于或等于键值的数字计数为： 4 6