업데이트 없이 범위 합계 쿼리를 위한 C++ 프로그램?

여기서 우리는 배열에서 인덱스 i에서 인덱스 j까지 요소의 합을 얻는 방법을 볼 것입니다. 이것은 기본적으로 범위 쿼리입니다. 인덱스 i에서 j까지 하나의 루프를 실행하고 합계를 계산하면 작업이 쉽습니다. 그러나 이러한 종류의 범위 쿼리가 여러 번 실행된다는 점에 주의해야 합니다. 따라서 언급한 방법을 사용하면 시간이 많이 걸립니다. 보다 효율적인 방법을 사용하여 이 문제를 해결하기 위해 먼저 누적 합계를 얻은 다음 일정 시간에 범위 합계를 찾을 수 있습니다. 아이디어를 얻을 수 있는 알고리즘을 살펴보겠습니다.

알고리즘

범위합(arr, i, j)

begin
   c_arr := cumulative sum of arr
   if i = 0, then
      return c_arr[j];
      return c_arr[j] – c_arr[i-1]
end

예시

#include<iostream>
using namespace std;
void cumulativeSum(int c_arr[], int arr[], int n){
   c_arr[0] = arr[0];
   for(int i = 1; i<n; i++){
      c_arr[i] = arr[i] + c_arr[i-1];
   }
}
int rangeSum(int c_arr[], int i, int j){
   if( i == 0){
      return c_arr[j];
   }
   return c_arr[j] - c_arr[i-1];
}
main() {
   int data[] = {5, 4, 32, 8, 74, 14, 23, 65};
   int n = sizeof(data)/sizeof(data[0]);
   int c_arr[n];
   cumulativeSum(c_arr, data, n); //get cumulative sum
   cout << "Range sum from index (2 to 5): " << rangeSum(c_arr, 2, 5) << endl;
   cout << "Range sum from index (0 to 3): " << rangeSum(c_arr, 0, 3) << endl;
   cout << "Range sum from index (4 to 7): " << rangeSum(c_arr, 4, 7) << endl;
}

출력

Range sum from index (2 to 5): 128
Range sum from index (0 to 3): 49
Range sum from index (4 to 7): 176