Truy vấn tổng phạm vi không có cập nhật bằng C ++

Trong bài này, chúng tôi sẽ đưa ra một mảng có kích thước n, sẽ là một số nguyên. Sau đó, chúng ta sẽ tính tổng các phần tử từ chỉ mục L đến chỉ mục R và thực hiện các truy vấn nhiều lần, hoặc chúng ta cần tính tổng của phạm vi đã cho từ [L, R]. Ví dụ -

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

Phương pháp tiếp cận để tìm ra giải pháp

Có hai giải pháp cho câu hỏi này. Cách đầu tiên là theo phương pháp Brute Force và theo phương pháp Tổng tiền tố (Hiệu quả).

Phương pháp tiếp cận vũ phu

Trong cách tiếp cận này, chúng tôi sẽ duyệt qua phạm vi đã cho và in ra tổng.

Ví dụ

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

Đầu ra

9
12

Giải thích về Quy tắc trên

Trong cách tiếp cận này, chúng tôi chỉ đơn giản là đi qua các phạm vi đã cho; trong trường hợp này, chương trình này tốt vì nó có độ phức tạp thời gian tìm kiếm O (N), trong đó N là kích thước của mảng đã cho. Tuy nhiên, điều này thay đổi khi chúng ta được cung cấp một số truy vấn Q thì độ phức tạp của chúng ta chuyển thành O (N * Q), trong đó Q là số lượng truy vấn và N là kích thước của mảng đã cho. Rất tiếc, độ phức tạp lần này không thể xử lý các ràng buộc cao hơn, vì vậy bây giờ chúng ta sẽ xem xét một cách tiếp cận hiệu quả sẽ phù hợp với các ràng buộc cao hơn.

Phương pháp tiếp cận hiệu quả

Trong cách tiếp cận này, chúng tôi sẽ tạo một mảng mới có tên tiền tố sẽ là mảng tổng tiền tố của chúng tôi và sau đó chúng tôi trả lời tổng của các phạm vi đã cho.

Ví dụ

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

Đầu ra

9
12

Giải thích về đoạn mã trên

Trong cách tiếp cận này, chúng tôi lưu trữ các giá trị tổng tiền tố trong một mảng được gọi là tiền tố. Bây giờ, mảng này làm cho chương trình của chúng ta rất hiệu quả vì điều này cho chúng ta độ phức tạp thời gian tìm kiếm là O (1), đây là độ phức tạp tốt nhất mà bạn có thể nhận được, và do đó khi chúng ta được cung cấp Q lượng truy vấn, thì độ phức tạp thời gian tìm kiếm của chúng ta sẽ trở thành O ( Q) trong đó Q là số lượng truy vấn.

Kết luận

Trong bài viết này, chúng tôi giải quyết một vấn đề để tìm các truy vấn tổng Phạm vi không có cập nhật bằng cách sử dụng mảng tổng tiền tố. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết này hữu ích.