इस समस्या में, हमें n इंटीजर्स का एक ऐरे और कुछ m क्वेरीज दी गई हैं। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो क्वेरीज द्वारा दी गई रेंज के मीन का इंटीग्रल मान (राउंड डाउन) गणना करे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट −
array = {5, 7, 8, 9, 10} m = 2; [0, 3], [2, 4]आउटपुट −
7 9
इस समस्या को हल करने के लिए हमारे पास दो तरीके हैं, एक सीधा है और दूसरा प्रीफिक्स सम का उपयोग कर रहा है।
सीधे दृष्टिकोण में, प्रत्येक क्वेरी के लिए, हम रेंज के स्टार्ट इंडेक्स से एंड इंडेक्स तक लूप करेंगे। और ऐरे के सभी इंटीजर्स को जोड़ेंगे और काउंट से विभाजित करेंगे। यह दृष्टिकोण ठीक काम करता है और परिणाम प्रिंट करता है लेकिन प्रभावी नहीं है।
प्रीफिक्स सम का उपयोग करके
इस दृष्टिकोण में, हम प्रीफिक्स सम ऐरे की गणना करेंगे जो ऐरे के सभी एलिमेंट्स का योग ith इंडेक्स तक संग्रहीत करेगा यानी प्रीफिक्ससम(4) इंडेक्स 4 तक सभी एलिमेंट्स का योग है।
अब, इस प्रीफिक्ससम ऐरे का उपयोग करके हम प्रत्येक क्वेरी के लिए मीन की गणना सूत्र का उपयोग करके करेंगे,
मीन = प्रीफिक्ससम[अपर] - प्रीफिक्ससम(लोअर-1) / अपर-लोअर+1
अपर और लोअर क्वेरी में दिए गए इंडेक्स हैं। यदि लोअर = 0, तो प्रीफिक्ससम(लोअर-1) = 0।
उदाहरण
हमारे समाधान के कार्य को स्पष्ट करने वाला प्रोग्राम,
#include <iostream> #define MAX 100 using namespace std; int prefixSum[MAX]; void initialisePrefixSum(int arr[], int n) { prefixSum[0] = arr[0]; for (int i = 1; i < n; i++) prefixSum[i] = prefixSum[i - 1] + arr[i]; } int queryMean(int l, int r) { int mean; if (l == 0) mean =(prefixSum[r]/(r+1)); else mean =((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1)); return mean; } int main() { int arr[] = {5, 7, 8, 9, 10 }; int n = sizeof(arr) / sizeof(arr[0]); initialisePrefixSum(arr, n); cout<<"Mean in 1st query: "<<queryMean(1, 4)<<endl; cout<<"Mean in 2st query: "<<queryMean(2, 4)<<endl; return 0; }आउटपुट
Mean in 1st query: 8 Mean in 2st query: 9
