C++ में रेंज योग की गणना

मान लीजिए हमारे पास एक पूर्णांक सरणी nums है, हमें उन रेंज योगों की संख्या ढूंढनी है जो रेंज [lower, upper] में दोनों समावेशी हैं। रेंज योग S(i, j) को nums में इंडेक्स i से इंडेक्स j तक के तत्वों के योग के रूप में परिभाषित किया गया है जहां i <= j।

तो यदि इनपुट [-3,6,-1] जैसा है, lower = -2 और upper = 2, तो परिणाम 2 होगा, क्योंकि रेंज [0,2] हैं, योग 2 है, [2,2], योग -2 है।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -

• एक फ़ंक्शन mergeIt() परिभाषित करें, जो सरणी prefix, start, mid, end, lower, upper लेगा,
• i := start, j := mid + 1
• temp := end - start + 1
• low := mid + 1, high := mid + 1
• k := 0
• आकार temp की एक सरणी arr परिभाषित करें।
• जब i <= mid, करें -
  • जब (low <= end और prefix[low] - prefix[i] < lower), करें -
    • low को 1 से बढ़ाएं
  • जब (high <= end और prefix[high] - prefix[i] <= upper), करें -
    • high को 1 से बढ़ाएं
  • जब (j <= end और prefix[j] < prefix[i]), करें -
    • arr[k] := prefix[j]
    • (j को 1 से बढ़ाएं)
    • (k को 1 से बढ़ाएं)
  • arr[k] := prefix[i]
  • (i को 1 से बढ़ाएं)
  • (k को 1 से बढ़ाएं)
  • count := count + high - low
• जब j <= end, करें -
  • arr[k] := prefix[j]
  • (k को 1 से बढ़ाएं)
  • (j को 1 से बढ़ाएं)
• i := 0 से आरंभ करें, जब i < temp, अपडेट करें (i को 1 से बढ़ाएं), करें -
  • prefix[start] := arr[i]
  • (start को 1 से बढ़ाएं)
• एक फ़ंक्शन merge() परिभाषित करें, जो prefix[], start, end, lower, upper लेगा,
  • यदि start >= end, तो लौटें
• mid := start + (end - start)
• फ़ंक्शन merge(prefix, start, mid, lower, upper) को कॉल करें
• फ़ंक्शन merge(prefix, mid + 1, end, lower, upper) को कॉल करें
• फ़ंक्शन mergeIt(prefix, start, mid, end, lower, upper) को कॉल करें
• मुख्य विधि से, निम्नलिखित करें -
• n := nums का आकार
• count := 0
• आकार n+1 की एक सरणी prefix परिभाषित करें।
• prefix[0] := 0
• i := 1 से आरंभ करें, जब i <= n, अपडेट करें (i को 1 से बढ़ाएं), करें -
  • prefix[i] := prefix[i - 1] + nums[i - 1]
• फ़ंक्शन merge(prefix, 0, n, lower, upper) को कॉल करें
• count लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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