इस लेख में, हम आकार n की एक सरणी देंगे, जो एक पूर्णांक होगा। फिर, हम इंडेक्स एल से इंडेक्स आर तक तत्वों के योग की गणना करेंगे और प्रश्नों को कई बार निष्पादित करेंगे, या हमें [एल, आर] से दी गई सीमा के योग की गणना करने की आवश्यकता होगी। उदाहरण के लिए -
Input : arr[] = {1, 2, 3, 4, 5}
L = 1, R = 3
L = 2, R = 4
Output : 9
12
Input : arr[] = {1, 2, 3, 4, 5}
L = 0, R = 4
L = 1, R = 2
Output : 15
5 समाधान खोजने के लिए दृष्टिकोण
इस प्रश्न के दो समाधान हैं। पहला ब्रूट फोर्स दृष्टिकोण और उपसर्ग योग (कुशल) दृष्टिकोण द्वारा है।
क्रूर फ़ोर्स अप्रोच
इस दृष्टिकोण में, हम दी गई सीमा को पार करेंगे और योग को प्रिंट करेंगे।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(int); // size of given array.
int L1 = 1, R1 = 3;
int L2 = 2, R2 = 4;
int sum = 0;
for(int i = L1; i <= R1; i++) // traversing through the first range.
sum += arr[i];
cout << sum << "\n";
sum = 0;
for(int i = L2; i <= R2; i++) // traversing through the second range.
sum += arr[i];
cout << sum << "\n";
} आउटपुट
9 12
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम केवल दी गई श्रेणियों से गुजर रहे हैं; इस मामले में, यह कार्यक्रम अच्छा है क्योंकि इसमें खोज समय जटिलता ओ (एन) है, जहां एन दिए गए सरणी का आकार है। फिर भी, यह तब बदल जाता है जब हमें कई प्रश्न Q दिए जाते हैं, तो हमारी जटिलता O (N * Q) में बदल जाती है, जहाँ Q प्रश्नों की संख्या है और N दिए गए सरणी का आकार है। दुर्भाग्य से, इस बार जटिलता उच्च बाधाओं को संभाल नहीं सकती है, इसलिए अब हम एक कुशल दृष्टिकोण पर गौर करेंगे जो उच्च बाधाओं के लिए काम करेगा।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम उपसर्ग नाम का एक नया सरणी बनाएंगे जो कि हमारा उपसर्ग योग सरणी होगा, और फिर हम दी गई श्रेणियों के योग का उत्तर देंगे।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(int); // size of given array.
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) // to avoid segmentation fault
cout << prefix[R1] - prefix[L1 - 1] << "\n";
else
cout << prefix[R1] << "\n";
if(L2) // avoiding segmentation fault.
cout << prefix[R2] - prefix[L2 - 1] << "\n";
else
cout << prefix[R2] << "\n";
} आउटपुट
9 12
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम उपसर्ग योग मानों को उपसर्ग नामक सरणी में संग्रहीत करते हैं। अब, यह सरणी हमारे कार्यक्रम को बहुत कुशल बनाती है क्योंकि यह हमें O(1) की खोज समय जटिलता देता है, जो कि आपको प्राप्त होने वाली सबसे अच्छी जटिलता है, और इसलिए जब हमें Q प्रश्नों की मात्रा दी जाती है, तो हमारी खोज समय जटिलता O हो जाती है ( Q) जहां Q प्रश्नों की संख्या है।
निष्कर्ष
इस लेख में, हम उपसर्ग योग सरणी का उपयोग करके अद्यतनों के बिना श्रेणी योग प्रश्नों को खोजने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।