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

আউটপুট − প্রদত্ত পরিসরে কী মানের থেকে ছোট বা সমান সংখ্যার সংখ্যা হল:9 7

ব্যাখ্যা − [9, 4 , 6 , 5] 3 থেকে 6 পর্যন্ত পরিসরের প্রতিনিধিত্ব করে এবং 9 হল প্রদত্ত সীমার মধ্যে 4র্থ ক্ষুদ্রতম সংখ্যা প্রদত্ত সেগমেন্ট পরিসরে সংখ্যা

নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি হল -

• একটি পূর্ণসংখ্যা টাইপ অ্যারে ঘোষণা. একটি অ্যারের আকার গণনা. পূর্ণসংখ্যার প্রকারের জোড়া গঠন করে একটি ভেক্টর টাইপ ভেরিয়েবল ঘোষণা করুন। অ্যারে থেকে ভেক্টরে ডেটা পুশ করতে FOR লুপ শুরু করুন৷

• প্রদত্ত ভেক্টর সাজান। MAX আকারের সাথে পূর্ণসংখ্যা ধরনের একটি ভেক্টর অ্যারে তৈরি করুন।

• ফাংশনটিকে generateTree(1, 0, size - 1, vec, tree) হিসাবে কল করুন এবং queryWrapper(2, 5, 2, size, vec, tree) এ getSmallestIndex সেট করুন।

• ইনপুট প্রিন্ট করুন[getSmallestIndex]।

• ফাংশনটিকে queryWrapper(1, 6, 4, size, vec, tree) হিসাবে কল করতে getSmallestIndex সেট করুন।

• অকার্যকর generateTree হিসাবে ফাংশনের ভিতরে (int treeIndex, int leftIndex, int rightIndex, vector> &a, vector tree[])

  • IF leftIndex to 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) এবং মার্জ(tree[2) করুন। * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin()। ট্রি সেট করুন[2 * treeIndex + 1].end(), back_inserter(tree[ treeIndex]))

• int calculateKSmallest (int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int কী, ভেক্টর ট্রি[])

  • IF startIndex থেকে endIndex চেক করুন তারপর ট্রি[treeIndex][0]

    দিন

  • মাঝামাঝি সেট করুন (startIndex + endIndex) / 2, last_in_query_range তে (upper_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryEnd) - ট্রি[2 * ট্রি ইনডেক্স].begin( ))

  • first_in_query_range সেট করুন (lower_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryStart)- ট্রি[2 * treeIndex].begin()) এবং M-এ শেষ_in_query_range - first_in_query_range

  • চেক করুন IF M এর চেয়ে বড় কি এর সমান তারপর calculateKSmallest (startIndex, mid, queryStart,queryEnd, 2 * treeIndex, কী, ট্রি) ফেরত দিন।

  • ELSE, তারপর calculateKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, কী - M, ট্রি) ফেরত দিন।

• int queryWrapper ফাংশনের ভিতরে(int queryStart, int queryEnd, int কী, int n, ভেক্টর> &a, vectortree[])

  • calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, কী, ট্রি)

উদাহরণ

#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