Sparsh Table là một cấu trúc dữ liệu, được sử dụng để đưa ra kết quả của các truy vấn phạm vi. Nó cung cấp kết quả của hầu hết các truy vấn phạm vi ở độ phức tạp O (logN). Đối với các truy vấn phạm vi tối đa, nó cũng có thể tính toán kết quả trong O (1).
Hướng dẫn này sẽ thảo luận về vấn đề truy vấn tổng phạm vi bằng cách sử dụng một bảng thưa thớt nơi chúng ta được cung cấp một mảng. Ví dụ, chúng ta cần tìm tổng của tất cả các phần tử trong phạm vi L và R.
Input: arr[ ] = { 2, 4, 1, 5, 6, 3 }
query(1, 3),
query(0,2),
query(1, 5).
Output: 10
7
19
Input: arr[ ] = { 1, 2, 3, 4, 1, 4 }
query(0, 2),
query(2,4),
query(3, 5).
Output: 6
8
9 Phương pháp tiếp cận để tìm giải pháp
Trước hết, chúng ta cần tạo một bảng thưa thớt để tìm kiếm các câu trả lời trong một bảng thưa thớt. Khi tạo bảng thưa thớt, chúng tôi sử dụng mảng 2-D để lưu trữ các câu trả lời. Trong bảng thưa thớt, chúng tôi ngắt các truy vấn theo lũy thừa 2. Sau khi tạo bảng thưa thớt, chúng tôi tìm kiếm các truy vấn trong bảng đó và tiếp tục thêm giá trị vào một biến với điều kiện (Left_index + 2 ^ n - 1 <=Right_index ) trong đó n là kích thước của cột của mảng 2-D.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include <bits/stdc++.h>
using namespace std;
// Maximum value of row of sparse table.
const int m = 1e5;
const int n = 16;
long long SPARSE[m][n + 1];
// query to be found with the help of a sparse table.
long long query(int l, int r){
long long sum = 0;
for (int i = n; i >= 0; i--) {
if (l + (1 << i) - 1 <= r) {
sum = sum + SPARSE[l][i];
l += 1 << i;
}
}
return sum;
}
int main(){
int arr[] = { 1, 2, 3, 4, 1, 4 };
int z = sizeof(arr) / sizeof(arr[0]);
// Building sparse table.
for (int i = 0; i < z; i++)
SPARSE[i][0] = arr[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= z - (1 << j); j++)
SPARSE[j][i] = SPARSE[j][i - 1] + SPARSE[j + (1 << (i - 1))][i - 1];
cout <<"Sum: " << query(0, 2) << endl;
cout <<"Sum: " << query(2, 4) << endl;
cout <<"Sum: " << query(3, 5) << endl;
return 0;
} Đầu ra
Sum: 6 Sum: 8 Sum: 4
Kết luận
Trong hướng dẫn này, chúng ta đã thảo luận về việc tạo một bảng thưa thớt rất hữu ích cho một loạt các truy vấn. Chúng tôi đã thảo luận về một cách tiếp cận đơn giản để giải quyết vấn đề này bằng cách tạo bảng thưa thớt và nhận các truy vấn đến kết quả từ bảng đó. Chúng tôi cũng đã thảo luận về chương trình C ++ cho vấn đề này mà chúng tôi có thể làm với các ngôn ngữ lập trình như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.