सी++ में ऐरे में न्यूनतम-अधिकतम रेंज क्वेरीज़

एक सरणी को देखते हुए Arr[] जिसमें N तत्व हैं। लक्ष्य क्वेरी की अनुक्रमणिका से न्यूनतम और अधिकतम मान ज्ञात करना है।

क्वेरी के अनुसार हमें शुरुआती इंडेक्स और एंडिंग इंडेक्स दिए गए हैं।

उदाहरण के लिए

में - 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 या qEnd1> num-1 या qStart1> qEnd1 )। अगर सही है तो क्वेरी में इनपुट रेंज अमान्य है।
अन्यथा, minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0) पर कॉल करें।
फ़ंक्शन minmaxFind (स्ट्रक्चर वैल्यू * रूट, इंट स्टार्ट टी, इंट एंड टी, इंट क्यूस्टार्ट, इंट क्यूएंड, इंट पॉज़) एक पुनरावर्ती फ़ंक्शन है। यह ट्री-रूट को विभाजित करने के लिए एक पॉइंटर लेता है, स्टार्ट टी और एंड टी के रूप में वर्तमान मूल्य के इंडेक्स को शुरू और समाप्त करता है।
यह क्वेरी श्रेणी में प्रारंभ और समाप्ति अनुक्रमणिका भी लेता है। खंड ट्री में मूल्य के वर्तमान सूचकांक में सूचकांक स्थिति है।
यदि (qStart <=startT) और यदि (qEnd>=endT) तो वर्तमान मान का खंड दी गई सीमा का हिस्सा है। तो उस मान में न्यूनतम और अधिकतम लौटाएं।
यदि यह सीमा से बाहर है तो वर्तमान मान को minVal और maxVal के साथ अपडेट करें।
यदि वर्तमान भाग दी गई सीमा के साथ ओवरलैप करता है तो :-
मध्य लें =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 के रूप में सेट करें।
वापसी अस्थायी।
फंक्शन सेगमेंटट्री(int arr2[], int startT2, int endT2, struct value *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