범위 합계 쿼리 - C++의 불변

정수 배열이 있다고 가정합니다. 인덱스 i에서 j까지 존재하는 요소의 합을 찾아야 합니다. 배열은 변경할 수 없으므로 요소가 변경되지 않으며 이러한 쿼리가 여러 개 있을 것이라는 두 가지 사항을 염두에 두어야 합니다. 따라서 많은 수의 쿼리에 대한 실행 시간에 신경을 써야 합니다. 배열이 A =[5, 8, 3, 6, 1, 2, 5]와 같다고 가정하고 쿼리가 (A, 0, 3)이면 5 + 8 + 3 + 6 =22가 됩니다.

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

• 배열 B 하나를 가져옵니다. B[i]는 0에서 i까지의 요소 합계를 저장합니다.
• 쿼리 수행 B[j] – B[i – 1]

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

예

#include <bits/stdc++.h>
using namespace std;
class NumArray {
   public:
   vector <int> pre;
   NumArray(vector<int>& nums) {
      pre.clear();
      int n = nums.size();
      pre.resize(n);
      for(int i = 0; i < n; i++){
         if(i == 0)pre[0] = nums[0];
         else
         pre[i] = pre[i - 1] + nums[i];
      }
   }
   int sumRange(int i, int j) {
      if(i == 0)return pre[j];
      return pre[j] - pre[i - 1];
   }
};
main(){
   vector<int> v = {5,8,3,6,1,2,5};
   NumArray na(v);
   cout<<na.sumRange(0,2)<<endl;
   cout<<na.sumRange(2,5)<<endl;
   cout<<na.sumRange(0,5)<<endl;
}

입력

Initialize it with [5,8,3,6,1,2,5]
Call sumRange(0,2)
sumRange(2,5)
sumRange(0,5)

출력

16
12
25