C++-এ অ্যারেতে Min-Max রেঞ্জ কুয়েরি

N উপাদান ধারণকারী একটি Arr[] অ্যারে দেওয়া আছে। লক্ষ্য হল কুয়েরির ইনডেক্স থেকে ন্যূনতম এবং সর্বোচ্চ মান খুঁজে বের করা।

কুয়েরি অনুযায়ী আমাদের শুরুর ইনডেক্স এবং শেষের ইনডেক্স দেওয়া আছে।

উদাহরণ

ইন - Arr[] = { 1, 2, 3, 4, 5 } QStart = 1 QEnd = 4

আউট -

ন্যূনতম মান : 2

সর্বোচ্চ মান : 5

ব্যাখ্যা - উপরের কুয়েরিতে শুরুর ইনডেক্স ১ এবং শেষের ইনডেক্স ৪। এই দুটি ইনডেক্সের মাঝপথে, Arr-এ ন্যূনতম মান ২ এবং সর্বোচ্চ মান ৫

ইন - Arr[] = { 10, 12, 3, 2, 5, 18 } QStart = 2 QEnd = 5

আউট -

ন্যূনতম মান : 2

সর্বোচ্চ মান : 18

ব্যাখ্যা - উপরের কুয়েরিতে শুরুর ইনডেক্স ২ এবং শেষের ইনডেক্স ৫। এই দুটি ইনডেক্সের মাঝপথে, Arr-এ ন্যূনতম মান ২ এবং সর্বোচ্চ মান ১৮

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

এই পদ্ধতিতে আমরা সেগমেন্ট ট্রি ব্যবহার করব lpos থেকে rpos রেঞ্জের জন্য কুয়েরি রেঞ্জে ন্যূনতম এবং সর্বোচ্চ মান খুঁজে বের করতে।

• ইনপুট অ্যারে Arr[] এবং কুয়েরি ইনডেক্স QStart এবং QEnd নিন।
• value টাইপের result নিন।
• value স্ট্রাকচারটি অ্যারেতে কুয়েরি ব্যবহার করে পাওয়া ন্যূনতম এবং সর্বোচ্চ মান সংরক্ষণ করতে ব্যবহৃত হয়।
• value স্ট্রাকচারটি অ্যারেতে কুয়েরি ব্যবহার করে পাওয়া ন্যূনতম এবং সর্বোচ্চ মান সংরক্ষণ করতে ব্যবহৃত হয়।
• minMax(struct value *root1, int num, int qStart1, int qEnd1) ফাংশনটি কুয়েরি ইনডেক্স নেয় এবং ইনডেক্স রেঞ্জ qStart1 এবং qEnd1-এর মাঝপথে অ্যারেতে ন্যূনতম এবং সর্বোচ্চ মান খুঁজে বের করে।
• চেক করুন if ( qStart1 < 0 OR qEnd1 > num-1 OR qStart1 > qEnd1 )। যদি সত্য হয় তবে কুয়েরিতে ইনপুট রেঞ্জ অবৈধ।
• অন্যথায়, minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0) কল করুন।
• minmaxFind(struct value *root, int startT, int endT, int qStart, int qEnd, int pos) একটি রিকার্সিভ ফাংশন। এটি সেগমেন্ট ট্রির পয়েন্টার নেয়- root, করেন্ট ভ্যালুর শুরুর এবং শেষ ইনডেক্স startT এবং endT হিসেবে।
• এটি কুয়েরি রেঞ্জে শুরুর এবং শেষ ইনডেক্সও নেয়। সেগমেন্ট ট্রিতে value-এর করেন্ট ইনডেক্স pos ইনডেক্সে থাকে।
• যদি (qStart <= startT) এবং (qEnd >= endT) হয় তবে করেন্ট value-এর সেগমেন্ট দেওয়া রেঞ্জের অংশ। তাই সেই value-এ ন্যূনতম এবং সর্বোচ্চ রিটার্ন করুন।
• যদি রেঞ্জের বাইরে থাকে তবে করেন্ট value কে minVal এবং maxVal দিয়ে আপডেট করুন।
• যদি করেন্ট অংশ দেওয়া রেঞ্জের সাথে ওভারল্যাপ করে তবে:-
• middl = startT + ( endT - startT )/2 নিন।
• p1 এবং p2 নিন 2*pos+1 এবং =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-এর ন্যূনতম হিসেবে।
• temp.maxVal সেট করুন lpos.maxVal এবং rpos.maxVal-এর সর্বোচ্চ হিসেবে।
• temp রিটার্ন করুন।
• segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2) ফাংশনটি arr2[] অ্যারের জন্য ইনডেক্স রেঞ্জ startT2 এবং endT2 এবং করেন্ট value পজিশন pos2 দিয়ে সেগমেন্ট ট্রি নির্মাণ করতে ব্যবহৃত হয়।
• *createTree(int arr0[], int num0) ফাংশনটি একটি দেওয়া অ্যারে arr0 থেকে সেগমেন্ট ট্রি নির্মাণ করতে ব্যবহৃত হয়। এই ফাংশন সেগমেন্ট ট্রির জন্য মেমরি অ্যালোকেট করে এবং মেমরি অ্যালোকেশনের জন্য segmentTree() কল করে।

উদাহরণ

#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