Truy vấn tổng phạm vi - Bất biến trong C ++

Giả sử chúng ta có một mảng các số nguyên. Chúng ta phải tìm tổng các phần tử có mặt từ chỉ số i đến j. Hai điều chúng ta phải ghi nhớ rằng mảng sẽ không thay đổi, vì vậy các phần tử sẽ không bị thay đổi và sẽ có nhiều truy vấn như vậy. Vì vậy, chúng ta phải quan tâm đến thời gian thực hiện cho một số lượng lớn các truy vấn. Giả sử mảng giống như A =[5, 8, 3, 6, 1, 2, 5], sau đó nếu truy vấn là (A, 0, 3), thì nó sẽ là 5 + 8 + 3 + 6 =22.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Lấy một mảng B. B [i] sẽ lưu trữ tổng các phần tử từ 0 đến i
• để thực hiện truy vấn B [j] - B [i - 1]

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

16
12
25