Range Sum Queries โดยไม่มีการอัปเดต ใช้ C++

ในบทความนี้ เราจะได้รับอาร์เรย์ขนาด n ซึ่งเป็นจำนวนเต็ม จากนั้นเราจะคำนวณผลรวมขององค์ประกอบจากดัชนี L ถึงดัชนี R และดำเนินการคิวรีหลายครั้ง หรือเราต้องคำนวณผลรวมของช่วงที่กำหนดจาก [L, R] ตัวอย่างเช่น:

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

วิธีการแก้ปัญหา

มีสองวิธีแก้ปัญหานี้ วิธีแรกคือ Brute Force และวิธีที่สองคือ Prefix Sum (วิธีที่มีประสิทธิภาพ)

วิธี Brute Force

ในวิธีนี้ เราจะเดินทางผ่านช่วงที่กำหนดและพิมพ์ผลรวม

ตัวอย่าง

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

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int); // ขนาดของอาร์เรย์ที่กำหนด
    int L1 = 1, R1 = 3;
    int L2 = 2, R2 = 4;
    int sum = 0;
    
    for(int i = L1; i <= R1; i++) // เดินทางผ่านช่วงแรก
        sum += arr[i];
    cout << sum << "\n";
    
    sum = 0;
    for(int i = L2; i <= R2; i++) // เดินทางผ่านช่วงที่สอง
        sum += arr[i];
    cout << sum << "\n";
}

ผลลัพธ์

9 12

คำอธิบายโค้ด

ในวิธีนี้ เราเพียงแค่เดินทางผ่านช่วงที่กำหนด ในกรณีนี้ โปรแกรมนี้ดีเพราะมีความซับซ้อนด้านเวลาในการค้นหา O(N) โดยที่ N คือขนาดของอาร์เรย์ที่กำหนด แต่สิ่งนี้จะเปลี่ยนเมื่อเราได้รับคิวรีจำนวนมาก Q ความซับซ้อนของเราจะกลายเป็น O(N×Q) โดยที่ Q คือจำนวนคิวรี และ N คือขนาดของอาร์เรย์ที่กำหนด น่าเสียดายที่ความซับซ้อนด้านเวลานี้ไม่สามารถจัดการกับข้อจำกัดที่สูงกว่าได้ ดังนั้นตอนนี้เราจะมาดูวิธีที่มีประสิทธิภาพซึ่งจะทำงานได้ดีกับข้อจำกัดที่สูงกว่า

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะสร้างอาร์เรย์ใหม่ชื่อ prefix ซึ่งจะเป็นอาร์เรย์ prefix sum แล้วเราตอบผลรวมของช่วงที่กำหนด

ตัวอย่าง

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

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int); // ขนาดของอาร์เรย์ที่กำหนด
    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) // เพื่อหลีกเลี่ยง segmentation fault
        cout << prefix[R1] - prefix[L1 - 1] << "\n";
    else
        cout << prefix[R1] << "\n";
    
    if(L2) // หลีกเลี่ยง segmentation fault
        cout << prefix[R2] - prefix[L2 - 1] << "\n";
    else
        cout << prefix[R2] << "\n";
}

ผลลัพธ์

9 12

คำอธิบายโค้ด

ในวิธีนี้ เราเก็บค่า prefix sum ไว้ในอาร์เรย์ที่ชื่อ prefix อาร์เรย์นี้ทำให้โปรแกรมของเรามีประสิทธิภาพมาก เพราะให้ความซับซ้อนด้านเวลาในการค้นหาเป็น O(1) ซึ่งเป็นความซับซ้อนที่ดีที่สุด ดังนั้นเมื่อเราได้รับคิวรีจำนวน Q ความซับซ้อนด้านเวลาในการค้นหาจะกลายเป็น O(Q) โดยที่ Q คือจำนวนคิวรี

สรุป

ในบทความนี้ เราแก้ปัญหาการหา Range sum queries โดยไม่มีการอัปเดต โดยใช้ Prefix sum array เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ธรรมดาและมีประสิทธิภาพ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ หวังว่าบทความนี้จะเป็นประโยชน์