C++ এ পরিসরের সমষ্টির গণনা

ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে সংখ্যা আছে, আমাদেরকে পরিসরের যোগফলের সংখ্যা খুঁজে বের করতে হবে যেটি পরিসীমা [নিম্ন, উপরের] উভয়ই অন্তর্ভুক্ত। ব্যাপ্তির যোগফল S(i, j) সূচক i থেকে সূচক j পর্যন্ত সংখ্যায় উপাদানের যোগফল হিসাবে সংজ্ঞায়িত করা হয় যেখানে i ≤ j।

সুতরাং যদি ইনপুটটি [-3,6,-1], নিম্ন =-2 এবং উপরের =2 এর মত হয়, তাহলে ফলাফল 2 হবে, যেমন রেঞ্জগুলি [0,2], যোগফল হল 2, [2, 2], যোগফল -2।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন mergeIt() সংজ্ঞায়িত করুন, এটি অ্যারে উপসর্গ, শুরু, মধ্য, শেষ, নিম্ন, উপরের,
• i :=শুরু, j :=মধ্য + 1
• temp :=end - start + 1
• নিম্ন :=মধ্য + 1, উচ্চ :=মধ্য + 1
• k :=0
• আকারের একটি অ্যারে অ্যারের সংজ্ঞা দিন:টেম্প।
• যখন i <=mid, do −
  • যখন (নিম্ন <=শেষ এবং উপসর্গ[নিম্ন] - উপসর্গ[i] <নিম্ন), −
    করুন
    • 1 দ্বারা কম বাড়ান
  • যখন (উচ্চ <=শেষ এবং উপসর্গ [উচ্চ] - উপসর্গ[i] <=উপরের), করুন −
    • 1 দ্বারা উচ্চ বৃদ্ধি
  • যখন (j <=শেষ এবং উপসর্গ[j] <উপসর্গ[i]), −
    করুন
    • arr[k] :=উপসর্গ[j]
    • (j 1 দ্বারা বাড়ান)
    • (k 1 দ্বারা বাড়ান)
  • arr[k] :=উপসর্গ[i]
  • (i 1 দ্বারা বাড়ান)
  • (k 1 দ্বারা বাড়ান)
  • গণনা :=গণনা + উচ্চ - নিম্ন
• যখন j <=শেষ, −
  করুন
  • arr[k] :=উপসর্গ[j]
  • (k 1 দ্বারা বাড়ান)
  • (j 1 দ্বারা বাড়ান)
• আরম্ভ করার জন্য i :=0, যখন i করুন
• প্রিফিক্স[start] :=arr[i]
• (1 দ্বারা শুরু বাড়ান)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int count = 0;
   void mergeIt(lli prefix[], lli start ,lli mid, lli end, lli lower, lli upper){
      lli i = start, j = mid + 1;
      lli temp = end - start + 1;
      lli low = mid + 1, high = mid + 1;
      lli k = 0;
      lli arr[temp];
      while(i <= mid){
         while(low <= end && prefix[low] - prefix[i] < lower) low++;
         while(high <= end && prefix[high] - prefix[i] <= upper) high++;
         while(j<= end && prefix[j] < prefix[i]){
            arr[k] = prefix[j];
            j++;
            k++;
         }
         arr[k] = prefix[i];
         i++;
         k++;
         count += high - low;
      }
      while(j <= end){
         arr[k] = prefix[j];
         k++;
         j++;
      }
      for(i = 0; i < temp; i++){
         prefix[start] = arr[i];
         start++;
      }
   }
   void merge(lli prefix[], lli start, lli end, lli lower, lli upper){
      if(start >= end)return;
      lli mid = start + (end - start) / 2;
      merge(prefix, start, mid, lower, upper);
      merge(prefix, mid + 1, end, lower, upper);
      mergeIt(prefix, start, mid, end, lower, upper);
   }
   int countRangeSum(vector<int>& nums, int lower, int upper) {
      lli n = nums.size();
      count = 0;
      lli prefix[n + 1];
      prefix[0] = 0;
      for(lli i = 1; i <= n; i++){
         prefix[i] = prefix[i - 1] + nums[i - 1];
      }
      merge(prefix, 0, n, lower, upper);
      return count;
   }
};
main(){
   Solution ob;
   vector<int> v = {-3,6,-1};
   cout << (ob.countRangeSum(v, -2, 2));
}

ইনপুট

{-3,6,-1}
-2
2

আউটপুট

2