सी ++ में सरणी में श्रेणी का मतलब

इस समस्या में, हमें n पूर्णांकों की एक सरणी और कुछ m प्रश्न दिए गए हैं। हमारा काम एक ऐसा प्रोग्राम बनाना है जो प्रश्नों द्वारा दी गई श्रेणियों के माध्य के अभिन्न मूल्य (राउंड डाउन) की गणना करता है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट -

array = {5, 7, 8, 9, 10}
m = 2; [0, 3], [2, 4]

आउटपुट -

7
9

इस समस्या को हल करने के लिए, हमारे पास दो तरीके हैं एक प्रत्यक्ष है और दूसरा उपसर्ग योग का उपयोग कर रहा है।

प्रत्यक्ष दृष्टिकोण में, प्रत्येक क्वेरी के लिए, हम प्रारंभ अनुक्रमणिका से श्रेणी के अंत अनुक्रमणिका तक लूप करेंगे। और सरणी के सभी पूर्णांक जोड़ें और गिनती से विभाजित करें। यह दृष्टिकोण ठीक काम करता है और परिणाम को प्रिंट करता है लेकिन यह प्रभावी नहीं है।

उपसर्ग का उपयोग करना

इस दृष्टिकोण में, हम उपसर्ग योग सरणी की गणना करेंगे जो सरणी के सभी तत्वों के योग को ith अनुक्रमणिका तक संग्रहीत करेगा अर्थात उपसर्ग योग (4) अनुक्रमणिका 4 तक सभी तत्वों का योग है।

अब, इस प्रीफ़िक्ससम सरणी का उपयोग करके हम सूत्र का उपयोग करके प्रत्येक क्वेरी के लिए माध्य की गणना करेंगे,

Mean = prefixSum[upper] - prefixSum(lower-1) / upper-lower+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