C++-এ রেঞ্জ সমের গণনা (Count of Range Sum)

রেঞ্জ সম কাউন্ট সমস্যা

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

উদাহরণ: [-3,6,-1], lower=-2, upper=2 → উত্তর ২ (রেঞ্জ: [0,2] যোগফল ২, [2,2] যোগফল -২)

সমাধানের পদ্ধতি (মার্জ সোর্ট + প্রিফিক্স সম)

• প্রিফিক্স সম অ্যারে prefix তৈরি করুন: prefix[i] = nums[0..i-1] এর যোগফল
• prefix[j] - prefix[i] = সাবঅ্যারে [i, j-1] এর যোগফল
• মার্জ সোর্টের মাধ্যমে prefix সর্ট করার সময়ই বৈধ জোড়া গণনা করুন
  • mergeIt ফাংশনে বাম ও ডান অংশ মার্জ করার আগে, প্রতিটি বাম উপাদানের জন্য ডান অংশে কতগুলো মান [lower, upper] রেঞ্জে আছে তা দ্বি-পয়েন্টার দিয়ে গণনা করুন
• মোট কাউন্ট ফেরত দিন

C++ কোড উদাহরণ

#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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {-3,6,-1};
    cout << (ob.countRangeSum(v, -2, 2));
    return 0;
}

ইনপুট

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

আউটপুট

2