C++의 범위 합계 개수

정수 배열 num이 있다고 가정하고 [lower, upper] 범위에 있는 범위 합계의 수를 찾아야 합니다. 범위 합 S(i, j)는 i ≤ j인 경우 인덱스 i에서 인덱스 j까지의 요소의 합으로 정의됩니다.

따라서 입력이 [-3,6,-1], lower =-2 및 upper =2와 같으면 범위가 [0,2]이므로 합계는 2, [2, 2], 합계는 -2입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• mergeIt() 함수를 정의하면 배열 접두사, 시작, 중간, 끝, 아래, 위,
• i :=시작, j :=중간 + 1
• temp :=끝 - 시작 + 1
• 낮음 :=중간 + 1, 높음 :=중간 + 1
• k :=0
• 크기:temp의 배열을 정의합니다.
• i <=mid인 동안 −
  • 동안(low <=end 및 prefix[low] - prefix[i]
  • 낮게 1씩 증가
• 동안(high <=end 및 prefix[high] - prefix[i] <=upper), −
  • 최대 1 증가
• 동안 (j <=end and prefix[j]
• arr[k] :=접두어[j]
• (j를 1씩 증가)
• (k를 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