रेंज सम क्वेरी - 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]
perform परफॉर्म करें

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class NumArray {
   public:
   vector <int> pre;
   NumArray(vector<int>& 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<int> 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;
}

इनपुट

Initialize it with [5,8,3,6,1,2,5]
Call sumRange(0,2)
sumRange(2,5)
sumRange(0,5)

आउटपुट

16
12
25