C++를 사용하여 업데이트가 없는 범위 합계 쿼리

이 기사에서는 정수가 될 크기 n의 배열을 제공할 것입니다. 그런 다음 인덱스 L에서 인덱스 R까지 요소의 합을 계산하고 쿼리를 여러 번 실행하거나 [L, R]에서 주어진 범위의 합을 계산해야 합니다. 예를 들어 -

Input : arr[] = {1, 2, 3, 4, 5}
   L = 1, R = 3
   L = 2, R = 4
Output : 9
   12

Input : arr[] = {1, 2, 3, 4, 5}
   L = 0, R = 4
   L = 1, R = 2
Output : 15
   5

해결책을 찾기 위한 접근 방식

이 질문에 대한 두 가지 해결책이 있습니다. 첫 번째는 Brute Force 방식과 Prefix sum(Efficient) 방식입니다.

무차별 대입 접근

이 접근 방식에서는 주어진 범위를 순회하고 합계를 출력합니다.

예

#include<bits/stdc++.h>

using namespace std;

int main() {
   int arr[] = {1, 2, 3, 4, 5};
   int n = sizeof(arr)/sizeof(int); // size of given array.
   int L1 = 1, R1 = 3;
   int L2 = 2, R2 = 4;
   int sum = 0;
   for(int i = L1; i <= R1; i++) // traversing through the first range.
      sum += arr[i];
   cout << sum << "\n";
   sum = 0;
   for(int i = L2; i <= R2; i++) // traversing through the second range.
      sum += arr[i];
   cout << sum << "\n";
}

출력

9
12

위 코드 설명

이 접근 방식에서는 단순히 주어진 범위를 횡단합니다. 이 경우 이 프로그램은 탐색 시간 복잡도가 O(N)이므로 좋은 프로그램입니다. 여기서 N은 주어진 배열의 크기입니다. 그러나 이것은 여러 쿼리 Q가 주어지면 복잡성이 O(N*Q)로 바뀝니다. 여기서 Q는 쿼리 수이고 N은 주어진 배열의 크기입니다. 불행히도 이 시간 복잡도는 더 높은 제약 조건을 처리할 수 없으므로 이제 더 높은 제약 조건에 대해 작동하는 효율적인 접근 방식을 살펴보겠습니다.

효율적인 접근

이 접근 방식에서는 접두사 합계 배열이 될 접두사라는 이름의 새 배열을 만든 다음 주어진 범위의 합에 답합니다.

예

#include<bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = {1, 2, 3, 4, 5};
   int n = sizeof(arr)/sizeof(int); // size of given array.
   int L1 = 1, R1 = 3;
   int L2 = 2, R2 = 4;
   int sum = 0;
   int prefix[n];
   for(int i = 0; i < n; i++){
      sum += arr[i];
      prefix[i] = sum;
   }

   if(L1) // to avoid segmentation fault
      cout << prefix[R1] - prefix[L1 - 1] << "\n";
   else
      cout << prefix[R1] << "\n";

   if(L2) // avoiding segmentation fault.
      cout << prefix[R2] - prefix[L2 - 1] << "\n";
   else
      cout << prefix[R2] << "\n";
}

출력

9
12

위 코드 설명

이 접근 방식에서는 접두사 합계 값을 접두사라는 배열에 저장합니다. 이제 이 배열은 우리가 얻을 수 있는 최고의 복잡성인 O(1)의 검색 시간 복잡성을 제공하므로 우리 프로그램을 매우 효율적으로 만듭니다. 따라서 Q 양의 쿼리가 주어지면 검색 시간 복잡성은 O( Q) 여기서 Q는 쿼리 수입니다.

결론

이 기사에서는 Prefix 합계 배열을 사용하여 업데이트 없이 범위 합계 쿼리를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.