C++ में रेंज सम क्वेरी - अपरिवर्तनीय

मान लीजिए हमारे पास पूर्णांकों का एक ऐरे है। हमें इंडेक्स i से j तक मौजूद तत्वों का योग ढूंढना है। दो बातें ध्यान में रखनी हैं कि ऐरे अपरिवर्तनीय होगा, इसलिए तत्व बदले नहीं जाएंगे, और ऐसी कई क्वेरी होंगी। इसलिए हमें बड़ी संख्या में क्वेरी के लिए निष्पादन समय का ध्यान रखना होगा। मान लीजिए ऐरे A = [5, 8, 3, 6, 1, 2, 5] है, तो यदि क्वेरी (A, 0, 3) है, तो यह 5 + 8 + 3 + 6 = 22 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक ऐरे B लें। B[i] 0 से i तक के तत्वों का योग स्टोर करेगा
• क्वेरी के लिए B[j] - B[i - 1] करें

आइए बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

उदाहरण

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

class NumArray { 
public: 
    vector pre; 
    
    NumArray(vector& nums) { 
        pre.clear(); 
        int n = nums.size(); 
        pre.resize(n); 
        for(int i = 0; i < n; i++){ 
            if(i == 0) pre[0] = nums[0]; 
            else 
                pre[i] = pre[i - 1] + nums[i]; 
        } 
    } 
    
    int sumRange(int i, int j) { 
        if(i == 0) return pre[j]; 
        return pre[j] - pre[i - 1]; 
    } 
}; 

main(){ 
    vector v = {5,8,3,6,1,2,5}; 
    NumArray na(v); 
    cout << na.sumRange(0,2) << endl; 
    cout << na.sumRange(2,5) << endl; 
    cout << na.sumRange(0,5) << endl; 
}

इनपुट

इसे [5,8,3,6,1,2,5] से इनिशियलाइज़ करें 
sumRange(0,2) कॉल करें 
sumRange(2,5) 
sumRange(0,5)

आउटपुट

16 12 25