Tổng số phạm vi trong C ++

Giả sử chúng ta có một nums mảng số nguyên, chúng ta phải tìm số lượng các tổng phạm vi nằm trong phạm vi [dưới, trên] cả bao gồm. Tổng phạm vi S (i, j) được định nghĩa là tổng các phần tử trong nums từ chỉ mục i đến chỉ mục j trong đó i ≤ j.

Vì vậy, nếu đầu vào là [-3,6, -1], thấp hơn =-2 và trên =2, thì kết quả sẽ là 2, vì phạm vi là [0,2], tổng là 2, [2, 2], tổng là -2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm mergeIt (), điều này sẽ nhận tiền tố mảng, bắt đầu, giữa, cuối, dưới, trên,
• i:=start, j:=mid + 1
• temp:=end - start + 1
• thấp:=giữa + 1, cao:=giữa + 1
• k:=0
• Xác định một dãy mảng có kích thước:temp.
• while i <=mid, do -
  • while (low <=end và prefix [low] - prefix [i]
  • tăng thấp 1
• while (high <=end và prefix [high] - prefix [i] <=upper), do -
  • tăng cao 1
• while (j <=end và prefix [j]
• arr [k]:=prefix [j]
• (tăng j lên 1)
• (tăng k thêm 1)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

2