N উপাদান ধারণকারী একটি অ্যারে Arr[] দেওয়া হয়েছে। লক্ষ্য হল ক্যোয়ারী সূচী থেকে সর্বনিম্ন এবং সর্বোচ্চ মান খুঁজে বের করা।
ক্যোয়ারী অনুসারে আমাদের প্রারম্ভিক সূচী এবং শেষ সূচী দেওয়া হয়।
উদাহরণস্বরূপ
এ − Arr[] ={ 1, 2, 3, 4, 5 } QStart =1 QEnd =4
আউট −
ন্যূনতম মান:2
সর্বোচ্চ মান:5
ব্যাখ্যা −উপরের প্রশ্নগুলিতে প্রারম্ভিক সূচক হল 1 এবং শেষ সূচক হল 4৷ এই দুটি সূচকের মধ্যে, Arr-এ সর্বনিম্ন মান হল 2 এবং সর্বাধিক মান হল 5
এ − Arr[] ={ 10, 12, 3, 2, 5, 18 } QStart =2 QEnd =5
আউট −
ন্যূনতম মান:2
সর্বোচ্চ মান:18
ব্যাখ্যা − উপরের প্রশ্নগুলিতে শুরুর সূচক হল 2 এবং শেষ সূচক হল 5৷ এই দুটি সূচকের মধ্যে, Arr-এ সর্বনিম্ন মান হল 2 এবং সর্বাধিক মান হল 18
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি হল -
এই পদ্ধতিতে আমরা প্রদত্ত ক্যোয়ারী পরিসরে ন্যূনতম এবং সর্বোচ্চ মান খুঁজে পেতে lpos থেকে rpos পরিসরের জন্য সেগমেন্ট ট্রি ব্যবহার করব৷
-
ইনপুট অ্যারে Arr[] নিন এবং QStart এবং QEnd সূচী জিজ্ঞাসা করুন।
-
টাইপ মানের ফলাফল নিন।
-
প্রদত্ত ক্যোয়ারী ব্যবহার করে একটি অ্যারেতে পাওয়া ন্যূনতম এবং সর্বোচ্চ মান সংরক্ষণ করতে কাঠামোর মান ব্যবহার করা হয়৷
-
প্রদত্ত ক্যোয়ারী ব্যবহার করে একটি অ্যারেতে পাওয়া ন্যূনতম এবং সর্বোচ্চ মান সংরক্ষণ করতে কাঠামোর মান ব্যবহার করা হয়৷
-
ফাংশন minMax(struct value *root1, int num, int qStart1, int qEnd1) ক্যোয়ারী সূচী নেয় এবং সূচী রেঞ্জ qStart1 এবং qEnd1 এর মধ্যে একটি অ্যারেতে সর্বনিম্ন এবং সর্বোচ্চ খুঁজে পায়৷
-
পরীক্ষা করুন ( qStart1 <0 OR qEnd1> num-1 বা qStart1> qEnd1)। যদি সত্য হয় তাহলে ক্যোয়ারীতে ইনপুট পরিসরটি অবৈধ।
-
অন্যথায়, minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0) কল করুন।
-
ফাংশন minmaxFind(struct value *root, int startT, int endT, int qStart, int qEnd, int pos) একটি পুনরাবৃত্ত ফাংশন। ট্রি-রুট সেগমেন্ট করার জন্য এটি একটি পয়েন্টার লাগে, startT এবং endT হিসাবে বর্তমান মানের শুরু এবং শেষ সূচক।
-
এটি ক্যোয়ারী পরিসরে একটি শুরু এবং শেষ সূচকও নেয়। সেগমেন্ট ট্রিতে মানের বর্তমান সূচকে ইনডেক্স পোস আছে।
-
যদি (qStart <=startT) এবং if( qEnd>=endT) তাহলে বর্তমান মানের সেগমেন্ট প্রদত্ত পরিসরের অংশ। তাই সেই মানের মধ্যে সর্বনিম্ন এবং সর্বোচ্চ রিটার্ন করুন।
-
যদি এটি সীমার বাইরে থাকে তবে বর্তমান মানটি minVal এবং maxVal দিয়ে আপডেট করুন।
-
যদি বর্তমান অংশ প্রদত্ত ব্যাপ্তির সাথে ওভারল্যাপ করে তাহলে :-
-
midl =startT + ( endT - startT )/2 নিন।
-
p1 এবং p2 কে 2*pos+1 এবং =2*pos+2 হিসাবে নিন।
-
lpos কে lpos =minmaxFind(root, startT, middl, qStart, qEnd, p1) এবং rpos কে minmaxFind(root, middl+1, endT, qStart, qEnd, p2) হিসাবে আপডেট করুন।
-
temp.minVal কে ন্যূনতম lpos.minVal এবং rpos.minVal হিসাবে সেট করুন।
-
temp.maxVal কে সর্বাধিক lpos.maxVal এবং rpos.maxVal হিসাবে সেট করুন।
-
রিটার্ন টেম্প।
-
ফাংশন segmentTree(int arr2[], int startT2, int endT2, struct মান *root2, int pos2) অ্যারে arr2[]-এর জন্য startT2 এবং endT2 হিসাবে সূচক পরিসীমা সহ একটি সেগমেন্ট ট্রি তৈরি করতে ব্যবহৃত হয় এবং বর্তমান মান অবস্থান হল pos2৷
-
ফাংশন *createTree(int arr0[], int num0) একটি প্রদত্ত অ্যারে arr0 থেকে একটি সেগমেন্ট ট্রি তৈরি করতে ব্যবহৃত হয়। এই ফাংশনটি সেগমেন্ট ট্রির জন্য মেমরি বরাদ্দ করে এবং মেমরি বরাদ্দের জন্য সেগমেন্ট ট্রি() কল করে।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
struct value{
int minVal;
int maxVal;
};
struct value minmaxFind(struct value *root, int startT, int endT, int qStart,
int qEnd, int pos){
struct value temp, lpos ,rpos;
if (qStart <= startT) {
if( qEnd >= endT)
{ return root[pos]; }
}
if (endT < qStart || startT > qEnd) {
temp.minVal = 9999;
temp.maxVal = -9999;
return temp;
}
int middl = startT + ( endT - startT )/2;
int p1=2*pos+1;
int p2=2*pos+2;
lpos = minmaxFind(root, startT, middl, qStart, qEnd, p1);
rpos = minmaxFind(root, middl+1, endT, qStart, qEnd, p2);
temp.minVal = (lpos.minVal<rpos.minVal) ? lpos.minVal : rpos.minVal ;
temp.maxVal = (lpos.maxVal>rpos.maxVal) ? lpos.maxVal : rpos.maxVal ;
return temp;
}
struct value minMax(struct value *root1, int num, int qStart1, int qEnd1){
struct value temp1;
if (qStart1 < 0 || qEnd1 > num-1 || qStart1 > qEnd1){
cout<<"Please enter Valid input!!";
temp1.minVal = 9999;
temp1.maxVal = -9999;
return temp1;
}
return minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0);
}
void segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2){
if (startT2 == endT2) {
root2[pos2].minVal = arr2[startT2];
root2[pos2].maxVal = arr2[startT2];
return ;
}
int p1=pos2*2+1;
int p2=pos2*2+2;
int middl2 = startT2+(endT2-startT2)/2;
segmentTree(arr2, startT2, middl2, root2, p1);
segmentTree(arr2, middl2+1, endT2, root2, p2);
root2[pos2].minVal = root2[p1].minVal<root2[p2].minVal ? root2[p1].minVal : root2[p2].minVal;
root2[pos2].maxVal = root2[p1].maxVal>root2[p2].maxVal ? root2[p1].maxVal : root2[p2].maxVal;
}
struct value *createTree(int arr0[], int num0) {
int height = (int)(ceil(log2(num0)));
int maxS = 2*(int)pow(2, height) - 1;
struct value *root0 = new struct value[maxS];
segmentTree(arr0, 0, num0-1, root0, 0);
return root0;
}
int main() {
int Arr[] = { 1, 2, 3, 4, 5 };
int length = sizeof(Arr)/sizeof(Arr[0]);
struct value *tree = createTree(Arr, length);
int QStart = 1;
int QEnd = 4;
struct value answer=minMax(tree, length, QStart, QEnd);
cout<<"Minimum Value : "<<answer.minVal<<endl;
cout<<"Maximum Value : "<<answer.maxVal;
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে
Minimum Value : 2 Maximum Value : 5
