C++ Range Sum Query ใช้ Sparse Table

Sparse Table เป็นโครงสร้างข้อมูล (Data Structure) ซึ่งใช้เพื่อให้ผลลัพธ์ของ range queries มันให้ผลลัพธ์ของ range queries ส่วนใหญ่ในความซับซ้อน O(log N) สำหรับ maximum range queries มันยังคำนวณผลลัพธ์ได้ใน O(1)

บทช่วยสอนนี้จะอภิปรายปัญหา range sum query โดยใช้ sparse table โดยที่เราได้รับอาร์เรย์ เราต้องหาผลรวมขององค์ประกอบทั้งหมดในช่วง 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

วิธีการหาคำตอบ

ก่อนอื่น เราต้องสร้าง sparse table เพื่อค้นหาคำตอบใน sparse table ในการสร้าง Sparse table เราใช้ 2-D array สำหรับเก็บคำตอบ ใน sparse table เราแยกคิวรีในกำลังของ 2 หลังจากสร้าง Sparse table แล้ว เราค้นหาคิวรีในตารางนั้นและเพิ่มค่าในตัวแปรอย่างต่อเนื่องภายใต้เงื่อนไข (Left_index + 2^n - 1 <= Right_index) โดยที่ n คือขนาดของคอลัมน์ของ 2-D array

ตัวอย่าง

โค้ด C++ สำหรับวิธีข้างต้น

#include <bits/stdc++.h>
using namespace std;

// ค่าสูงสุดของแถวของ sparse table
const int m = 1e5;
const int n = 16;
long long SPARSE[m][n + 1];

// query ที่จะหาด้วยความช่วยเหลือของ 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]);
    // สร้าง 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

สรุป

ในบทช่วยสอนนี้ เราอภิปรายการสร้าง sparse table ที่มีประโยชน์มากสำหรับ range queries เราอภิปรายวิธีง่ายๆ ในการแก้ปัญหานี้โดยการสร้าง sparse table และได้ผลลัพธ์คิวรีจากตารางนั้น เรายังอภิปรายโปรแกรม C++ สำหรับปัญหานี้ซึ่งเราสามารถทำได้กับภาษาโปรแกรมมิ่งอย่าง C, Java, Python ฯลฯ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์