C++でソートツリーをマージ

整数配列、セグメントの開始ポインタと終了ポインタのセット、およびキー値が与えられます。ここでの問題の説明は、指定されたキー値以下の指定された範囲内のすべての値を見つけることです。

例を挙げて理解しましょう

入力 − arr [] ={7、8、1、4、6、8、10}

セグメント1：開始=2、終了=4、k =2

セグメント2：開始=1、終了=6、k =3

出力 −指定された範囲内のキー値以下の数のカウントは2 6

説明 − [8、1、4]は2から4の範囲を表し、2は範囲の2番目に小さい数値です[7、8、1、4、6、8]は1から6の範囲を表し、6は3番目です範囲内の最小数

入力 − 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は3番目に小さい数値です指定されたセグメント範囲の番号

以下のプログラムで使用されるアプローチは次のとおりです-

• 整数型配列を宣言します。配列のサイズを計算します。整数型のペアを形成するベクトル型変数を宣言します。 FORループを開始して、データを配列からベクトルにプッシュします。

• 指定されたベクトルを並べ替えます。 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）として呼び出します。

• 関数内でvoidgenerateTree（int treeIndex、int leftIndex、int rightIndex、vector >＆a、vector tree []）

  • IF leftIndexをrightIndexにチェックしてから、settree [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（）。set tree [2 * treeIndex + 1] .end（）、back_inserter（tree [ treeIndex]））

• 関数内でintcalculateKSmallest（int startIndex、int endIndex、int queryStart、int queryEnd、int treeIndex、int key、vector tree []）

  • IF startIndexを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

  • Mがキーと等しいかどうかを確認してからcalculateKSmallest（startIndex、mid、queryStart、queryEnd、2 * treeIndex、key、tree）を返します

  • ELSEの場合、calculateKSmallest（mid + 1、endIndex、queryStart、queryEnd、2 * treeIndex + 1、key --M、tree）を返します。

• 関数内intqueryWrapper（int queryStart、int queryEnd、int key、int n、vector >＆a、vector 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