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 Method

이 방법에서는 주어진 범위에 대해 반복하고 합계를 인쇄합니다.

Example

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

Output

9
12

위 코드에 대한 설명

이 접근 방식에서는 주어진 범위를 반복합니다. 이 경우 검색 시간 복잡도는 O(N)이므로 이 프로그램은 좋습니다. 주어진 배열의 크기. 그럼에도 불구하고 여러 쿼리 Q가 주어지면 상황이 바뀌고 복잡성은 O(N*Q)가 됩니다. 여기서 Q는 쿼리 수이고 N은 주어진 배열의 크기입니다. 불행하게도 이러한 시간 복잡도는 더 높은 제약 조건을 처리할 수 없으므로 이제 더 높은 제약 조건에 대한 효율적인 방법을 살펴보겠습니다.

효율적인 방법

이 방법에서는 접두사와 배열 역할을 할 접두사라는 새 배열을 만든 다음 주어진 범위의 합에 답합니다.

Example

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

Output

9
12

위 코드 설명

이 방법에서는 prefix라는 배열에 prefix와 값을 저장합니다. 이제 이 배열은 우리가 얻을 수 있는 최고의 복잡성인 O(1)의 검색 시간 복잡도를 제공하므로 프로그램을 매우 효율적으로 만듭니다. 따라서 Q 쿼리가 제공되면 검색 시간 복잡도는 O(Q)가 됩니다. , 여기서 Q는 쿼리 수입니다.

결론

이 기사에서는 접두사와 배열을 사용하여 업데이트 없이 범위와 쿼리를 찾는 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 완전한 솔루션(공통적이고 효율적인)을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 C++를 사용하여 다음을 번역합니다. 업데이트 없이 간격 합계 쿼리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!