C++-এ অ্যারেতে পরিসরের গড়

এই সমস্যায়, আমাদেরকে n পূর্ণসংখ্যার একটি অ্যারে এবং কিছু m প্রশ্ন দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা কোয়েরিগুলির দ্বারা প্রদত্ত রেঞ্জগুলির গড়গুলির অবিচ্ছেদ্য মান (রাউন্ড ডাউন) গণনা করে৷

সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,

ইনপুট −

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

আউটপুট −

7
9

এই সমস্যাটি সমাধান করার জন্য, আমাদের কাছে দুটি পদ্ধতি রয়েছে একটি হল সরাসরি এবং অন্যটি হল উপসর্গ যোগ।

প্রত্যক্ষ পদ্ধতিতে, প্রতিটি প্রশ্নের জন্য, আমরা সূচনা সূচক থেকে পরিসরের শেষ সূচকে লুপ করব। এবং অ্যারের সমস্ত পূর্ণসংখ্যা যোগ করুন এবং গণনা দ্বারা ভাগ করুন। এই পদ্ধতিটি সূক্ষ্ম কাজ করে এবং ফলাফল প্রিন্ট করে কিন্তু এটি কার্যকর নয়৷

উপসর্গ ব্যবহার করে

এই পদ্ধতিতে, আমরা উপসর্গ সমষ্টি অ্যারে গণনা করব যা ith সূচক পর্যন্ত অ্যারের সমস্ত উপাদানের যোগফল সংরক্ষণ করবে অর্থাৎ prefixSum(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