Sparsh Table เป็นโครงสร้างข้อมูลซึ่งใช้เพื่อแสดงผลลัพธ์ของการสืบค้นช่วง ให้ผลลัพธ์ของการสืบค้นช่วงส่วนใหญ่ในความซับซ้อน O(logN) สำหรับการค้นหาช่วงสูงสุด ยังสามารถคำนวณผลลัพธ์ใน O(1)
บทช่วยสอนนี้จะกล่าวถึงปัญหาของคิวรีผลรวมของช่วงโดยใช้ตารางกระจัดกระจายซึ่งเราได้รับอาร์เรย์ เราจำเป็นต้องหาผลรวมขององค์ประกอบทั้งหมดในช่วง L และ 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 แนวทางในการหาแนวทางแก้ไข
ประการแรก เราต้องสร้างตารางกระจัดกระจายเพื่อค้นหาคำตอบในตารางกระจัดกระจาย ในการสร้างตารางแบบกระจาย เราใช้อาร์เรย์ 2 มิติเพื่อเก็บคำตอบ ในตารางแบบกระจาย เราทำลายการสืบค้นด้วยกำลังของ 2 หลังจากสร้างตารางแบบกระจาย เราจะค้นหาข้อความค้นหาในตารางนั้นและยังคงเพิ่มค่าในตัวแปรตามเงื่อนไขของ ( Left_index + 2^n - 1 <=Right_index ) โดยที่ n คือขนาดของคอลัมน์ของอาร์เรย์ 2 มิติ
ตัวอย่าง
รหัส C++ สำหรับแนวทางข้างต้น
#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;
} ผลลัพธ์
Sum: 6 Sum: 8 Sum: 4
บทสรุป
ในบทช่วยสอนนี้ เราได้พูดถึงการสร้างตารางแบบกระจายซึ่งมีประโยชน์มากสำหรับคิวรีช่วงต่างๆ เราได้พูดคุยถึงแนวทางง่ายๆ ในการแก้ปัญหานี้โดยการสร้างตารางแบบกระจัดกระจายและรับการสืบค้นจากตารางนั้น เรายังพูดถึงโปรแกรม C++ สำหรับปัญหานี้ ซึ่งเราสามารถทำได้ด้วยภาษาโปรแกรม เช่น C, Java, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
