C++ का उपयोग करके अपडेट के बिना रेंज सम क्वेरी

इस लेख में, हम आकार n का एक एरे देंगे, जो एक पूर्णांक होगा। फिर, हम इंडेक्स L से इंडेक्स R तक के तत्वों का योग निकालेंगे और क्वेरी को कई बार निष्पादित करेंगे, या हमें दिए गए रेंज [L, R] का योग निकालना होगा। उदाहरण के लिए:

इनपुट: arr[] = {1, 2, 3, 4, 5}   L = 1, R = 3   L = 2, R = 4
आउटपुट: 9   12

इनपुट: arr[] = {1, 2, 3, 4, 5}   L = 0, R = 4   L = 1, R = 2
आउटपुट: 15   5

समाधान का दृष्टिकोण

इस प्रश्न के दो समाधान हैं। पहला ब्रूट फोर्स दृष्टिकोण द्वारा और दूसरा प्रीफिक्स सम (कुशल) दृष्टिकोण द्वारा।

ब्रूट फोर्स दृष्टिकोण

इस दृष्टिकोण में, हम दिए गए रेंज के माध्यम से ट्रैवर्स करेंगे और योग प्रिंट करेंगे।

उदाहरण

#include<bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int); // दिए गए एरे का आकार।
    int L1 = 1, R1 = 3;
    int L2 = 2, R2 = 4;
    int sum = 0;
    
    for(int i = L1; i <= R1; i++) // पहली रेंज के माध्यम से ट्रैवर्स करना।
        sum += arr[i];
    
    cout << sum << "\n";
    sum = 0;
    
    for(int i = L2; i <= R2; i++) // दूसरी रेंज के माध्यम से ट्रैवर्स करना।
        sum += arr[i];
    
    cout << sum << "\n";
}

आउटपुट

9 12

उपरोक्त कोड की व्याख्या

इस दृष्टिकोण में, हम केवल दिए गए रेंज के माध्यम से ट्रैवर्स कर रहे हैं; इस मामले में, यह प्रोग्राम अच्छा है क्योंकि इसकी खोज समय जटिलता O(N) है, जहां N दिए गए एरे का आकार है। लेकिन यह तब बदल जाता है जब हमें कई क्वेरी Q दी जाती हैं, तब हमारी जटिलता O(N*Q) हो जाती है, जहां Q क्वेरी की संख्या है और N दिए गए एरे का आकार है। दुर्भाग्य से, यह समय जटिलता उच्च प्रतिबंधों को संभाल नहीं सकती, इसलिए अब हम एक कुशल दृष्टिकोण देखेंगे जो उच्च प्रतिबंधों के लिए भी काम करेगा।

कुशल दृष्टिकोण

इस दृष्टिकोण में, हम prefix नामक एक नया एरे बनाएंगे जो हमारा प्रीफिक्स सम एरे होगा, और फिर हम दिए गए रेंज के योग का उत्तर देंगे।

उदाहरण

#include<bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int); // दिए गए एरे का आकार।
    int L1 = 1, R1 = 3;
    int L2 = 2, R2 = 4;
    int sum = 0;
    int prefix[n];
    
    for(int i = 0; i < n; i++){
        sum += arr[i];
        prefix[i] = sum;
    }
    
    if(L1) // सेगमेंटेशन फॉल्ट से बचने के लिए
        cout << prefix[R1] - prefix[L1 - 1] << "\n";
    else
        cout << prefix[R1] << "\n";
    
    if(L2) // सेगमेंटेशन फॉल्ट से बचना।
        cout << prefix[R2] - prefix[L2 - 1] << "\n";
    else
        cout << prefix[R2] << "\n";
}

आउटपुट

9 12

उपरोक्त कोड की व्याख्या

इस दृष्टिकोण में, हम प्रीफिक्स सम मानों को prefix नामक एरे में स्टोर करते हैं। अब यह एरे हमारे प्रोग्राम को बहुत कुशल बनाता है क्योंकि यह हमें O(1) की खोज समय जटिलता देता है, जो कि सबसे अच्छी जटिलता है जो आप प्राप्त कर सकते हैं, और इसलिए जब हमें Q मात्रा में क्वेरी दी जाती हैं, तो हमारी खोज समय जटिलता O(Q) हो जाती है जहां Q क्वेरी की संख्या है।

निष्कर्ष

इस लेख में, हम प्रीफिक्स सम एरे का उपयोग करके अपडेट के बिना रेंज सम क्वेरी की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य और कुशल) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।