C++ में सरणी में मिन-मैक्स रेंज क्वेरीज़

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 लें।
• value प्रकार का परिणाम लें।
• स्ट्रक्चर value का उपयोग सरणी में मिले न्यूनतम और अधिकतम मान को संग्रहीत करने के लिए किया जाता है जो दिए गए क्वेरी का उपयोग करता है।
• फंक्शन minMax(struct value *root1, int num, int qStart1, int qEnd1) क्वेरी सूचकांक लेता है और इंडेक्स रेंज qStart1 और qEnd1 के बीच सरणी में न्यूनतम और अधिकतम ढूंढता है।
• जांचें यदि (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 को लेता है, करंट value के प्रारंभिक और अंतिम सूचकांक startT और endT के रूप में।
• यह क्वेरी रेंज में प्रारंभिक और अंतिम सूचकांक भी लेता है। सेगमेंट ट्री में value का वर्तमान सूचकांक pos है।
• यदि (qStart <= startT) AND if( qEnd >= endT) तो करंट value का सेगमेंट दी गई रेंज का हिस्सा है। तो उस value में न्यूनतम और अधिकतम लौटाएं।
• यदि यह रेंज से बाहर है तो करंट value को minVal और maxVal से अपडेट करें।
• यदि करंट हिस्सा दी गई रेंज के साथ ओवरलैप करता है तो:
  • middl = 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 के अधिकतम के रूप में सेट करें।
  • 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