在C++中的合并排序树

We are given an integer array, a set of segment start and end pointers and a key value and the problem statement here is to find all the values in the given range which are smaller than or equal to the given key value.

Let us understand with example

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

立即学习“C++免费学习笔记（深入）”；

Output − Count of number which are smaller than or equal to key value in the given range are 2 6

Explanation − [8, 1, 4] represents the range from 2 to 4 and 2 is the 2nd smallest number in the range [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

输出 - 在给定范围内小于或等于关键值的数字的数量为：9 7

解释 - [9, 4 , 6 , 5]代表从3到6的范围，9是给定范围内第四小的数字 [7 , 9, 4 , 6 ] 表示从2到4的范围，7是给定段范围中第3小的数字

下面程序中使用的方法如下：

• 声明一个整数类型的数组。计算数组的大小。声明一个向量类型的变量，形成整数类型的对。开始FOR循环，将数据从数组推送到向量中。

• 对给定的向量进行排序。创建一个整数类型的向量数组，大小为MAX。

• 调用函数generateTree(1, 0, size - 1, vec, tree)，并将getSmallestIndex设置为queryWrapper(2, 5, 2, size, vec, tree)。

• 打印input[getSmallestIndex]。

  

  云网OA

  采用JSP开发的办公自动化产品、基于B/S结构，运行环境：JDK v1.5、Tomcat v5.5、MySQL v4.1，三者均为以上版本其他相关内容：可视化流程设计： 流程支持串签、会签和分支流程，可以设置流程节点的修改、删除权限，并可指定流程中各个用户在表单中可以填写的域。智能表单所见即所得设计： 智能设计，自动在数据库中生成表格，方便优化程序 公共交流： 集论坛、博客、聊天室于一体文件柜：C

  下载

• 将getSmallestIndex设置为调用函数queryWrapper(1, 6, 4, size, vec, tree)。

• 在函数generateTree(int treeIndex, int leftIndex, int rightIndex, vector > &a, vector tree[])内部

  • 检查IF leftIndex to rightIndex，然后设置 tree[treeIndex].push_back(a[leftIndex].second) and return

  • Set midValue to (leftIndex + rightIndex) / 2and call generateTree(2 * treeIndex, leftIndex, midValue, a, tree), generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree) and merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(). Set tree[2 * treeIndex + 1].end(),back_inserter(tree[treeIndex]))

• Inside the function as int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector tree[])

  • Check IF startIndex to endIndex then return tree[treeIndex][0]

  • Set mid to (startIndex + endIndex) / 2, last_in_query_range to (upper_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin())

  • set first_in_query_range to (lower_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()) and M to last_in_query_range - first_in_query_range

  • Check IF M greater than equals to key then return calculateKSmallest(startIndex, mid, queryStart,queryEnd, 2 * treeIndex, key, tree)

  • ELSE, then return calculateKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree).

• Inside the function int queryWrapper(int queryStart, int queryEnd, int key, int n, vector > &a, vectortree[])

  • return call to the function calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree)

Example

#include 
using namespace std;
const int MAX = 1000;
void generateTree(int treeIndex, int leftIndex, int rightIndex, vector > &a, vector 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 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 > &a, vector 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 > vec;
   for (int i = 0; i < size; i++) {
      vec.push_back(make_pair(input[i], i));
   }
   sort(vec.begin(), vec.end());
   vector 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:"<
输出
如果我们运行上述代码，将会生成以下输出
Count of number which are smaller than or equal to key value in the given range are:
4
6