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

मान लीजिए कि हमारे पास एक पूर्णांक सरणी संख्याएँ हैं, हमें श्रेणी योगों की संख्या ज्ञात करनी है जो सीमा [निचले, ऊपरी] दोनों में शामिल हैं। रेंज योग S(i, j) को इंडेक्स i से इंडेक्स j तक के अंकों में तत्वों के योग के रूप में परिभाषित किया गया है, जहां i j.

तो अगर इनपुट [-3,6,-1], निचला =-2 और ऊपरी =2 जैसा है, तो परिणाम 2 होगा, क्योंकि श्रेणियां [0,2] हैं, योग 2 है, [2, 2], योग -2 है।

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

• एक फ़ंक्शन मर्ज इट () को परिभाषित करें, यह सरणी उपसर्ग, प्रारंभ, मध्य, अंत, निचला, ऊपरी,
लेगा
• i :=start, j :=mid + 1
• अस्थायी:=अंत - प्रारंभ + 1
• निम्न:=मध्य + 1, उच्च:=मध्य + 1
• k :=0
• आकार की एक सरणी एरर परिभाषित करें:अस्थायी।
• जबकि मैं <=बीच में, −
  . करें
  • जबकि (निम्न <=अंत और उपसर्ग [निम्न] - उपसर्ग [i] <निचला), करते हैं -
    • 1 से कम बढ़ाएं
  • जबकि (उच्च <=अंत और उपसर्ग [उच्च] - उपसर्ग [i] <=ऊपरी), करते हैं −
    • ऊंचाई 1 से बढ़ाएं
  • जबकि (j <=अंत और उपसर्ग[j] <उपसर्ग[i]), करते हैं −
    • arr[k] :=उपसर्ग[j]
    • (j को 1 से बढ़ाएं)
    • (k 1 से बढ़ाएं)
  • arr[k] :=उपसर्ग[i]
  • (मैं 1 से बढ़ाएँ)
  • (k 1 से बढ़ाएं)
  • गिनती :=गिनती + उच्च-निम्न
• जबकि j <=समाप्त होता है, −
  . करें
  • arr[k] :=उपसर्ग[j]
  • (k 1 से बढ़ाएं)
  • (j को 1 से बढ़ाएं)
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• उपसर्ग[शुरू] :=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