C++ में रेंज सम क्वेरीज विदाउट अपडेट्स

समस्या विवरण

यहां हम देखेंगे कि सरणी में इंडेक्स i से इंडेक्स j तक के तत्वों का योग कैसे प्राप्त करें। यह मूल रूप से रेंज क्वेरी है। कार्य केवल इंडेक्स i से j तक एक लूप चलाकर और योग की गणना करके आसान है। लेकिन हमें इस बात का ध्यान रखना होगा कि इस तरह की रेंज क्वेरी कई बार निष्पादित की जाएगी। इसलिए यदि हम उल्लिखित विधि का उपयोग करते हैं, तो इसमें बहुत समय लगेगा। इस समस्या को अधिक कुशल तरीके से हल करने के लिए हम पहले संचयी योग प्राप्त कर सकते हैं, फिर रेंज योग स्थिर समय में पाया जा सकता है।

एल्गोरिदम

rangeSum(arr, i, j):
Begin
    c_arr := arr का संचयी योग
    if i == 0:
        return c_arr[j]
    return c_arr[j] - c_arr[i-1]
End

उदाहरण

#include <iostream>
#include <vector>
using namespace std;

void cumulativeSum(int c_arr[], int arr[], int n) {
    c_arr[0] = arr[0];
    for(int i = 1; i < n; i++) {
        c_arr[i] = arr[i] + c_arr[i-1];
    }
}

int rangeSum(int c_arr[], int i, int j) {
    if(i == 0) {
        return c_arr[j];
    }
    return c_arr[j] - c_arr[i-1];
}

int main() {
    int data[] = {5, 4, 32, 8, 74, 14, 23, 65};
    int n = sizeof(data) / sizeof(data[0]);
    int c_arr[n];

    cumulativeSum(c_arr, data, n);  // संचयी योग प्राप्त करें

    cout << "Range sum from index (2 to 5): " << rangeSum(c_arr, 2, 5) << endl;
    cout << "Range sum from index (0 to 3): " << rangeSum(c_arr, 0, 3) << endl;
    cout << "Range sum from index (4 to 7): " << rangeSum(c_arr, 4, 7) << endl;

    return 0;
}

आउटपुट

Range sum from index (2 to 5): 128
Range sum from index (0 to 3): 49
Range sum from index (4 to 7): 176

सत्यापन

सरणी: [5, 4, 32, 8, 74, 14, 23, 65]
संचयी: [5, 9, 41, 49, 123, 137, 160, 225]

Range (2,5): 32+8+74+14 = 128 = c_arr[5] - c_arr[1] = 137 - 9 = 128 ✓
Range (0,3): 5+4+32+8 = 49 = c_arr[3] = 49 ✓
Range (4,7): 74+14+23+65 = 176 = c_arr[7] - c_arr[3] = 225 - 49 = 176 ✓

आधुनिक C++ दृष्टिकोण

#include <iostream>
#include <vector>
#include <numeric>  // partial_sum के लिए

class RangeSumQuery {
    vector<long long> prefix;

public:
    RangeSumQuery(const vector<int>& arr) {
        prefix.resize(arr.size() + 1);
        prefix[0] = 0;
        partial_sum(arr.begin(), arr.end(), prefix.begin() + 1);
    }

    long long query(int l, int r) const {  // 0-इंडेक्स्ड, समावेशी
        return prefix[r + 1] - prefix[l];
    }
};

int main() {
    vector<int> data = {5, 4, 32, 8, 74, 14, 23, 65};
    RangeSumQuery rsq(data);

    cout << rsq.query(2, 5) << endl;  // 128
    cout << rsq.query(0, 3) << endl;  // 49
    cout << rsq.query(4, 7) << endl;  // 176
}

जटिलता विश्लेषण

अनुप्रयोग

• सबअरे योग क्वेरीज
• इमेज प्रोसेसिंग (इंटीग्रल इमेज)
• डेटाबेस रेंज क्वेरीज
• प्रतिस्पर्धी प्रोग्रामिंग