โปรแกรม C++ สำหรับ Range Sum Queries โดยไม่มีการอัปเดต

ที่นี่เราจะดูวิธีหาผลรวมขององค์ประกอบจากดัชนี i ถึงดัชนี j ในอาร์เรย์ นี่คือ range query แบบพื้นฐาน ง่ายดายด้วยการรันลูปหนึ่งจากดัชนี i ถึง j และคำนวณผลรวม แต่เราต้องคำนึงถึงว่าการ query แบวนี้จะทำหลายครั้ง หากใช้วิธีที่กล่าวมา จะใช้เวลามากเกินไป เพื่อแก้ปัญหาแบบมีประสิทธิภาพมากขึ้น เราสามารถหาผลรวมสะสม (cumulative sum) ก่อน แล้ว range sum จะหาได้ในเวลาคงที่ (constant time) มาดูอัลกอริทึม

อัลกอริทึม

rangeSum(arr, i, j)

begin
    c_arr := cumulative sum of arr
    if i = 0, then
        return c_arr[j];
    return c_arr[j] - c_arr[i-1]
end

ตัวอย่าง

#include<iostream>
using namespace std;

void cumulativeSum(int c_arr[], int arr[], int n) {
    c_arr[0] = arr[0];
    for(int i = 1; i < n; i++) {
        c_arr[i] = arr[i] + c_arr[i-1];
    }
}

int rangeSum(int c_arr[], int i, int j) {
    if(i == 0) {
        return c_arr[j];
    }
    return c_arr[j] - c_arr[i-1];
}

int main() {
    int data[] = {5, 4, 32, 8, 74, 14, 23, 65};
    int n = sizeof(data) / sizeof(data[0]);
    int c_arr[n];
    cumulativeSum(c_arr, data, n); // get cumulative sum
    cout << "Range sum from index (2 to 5): " << rangeSum(c_arr, 2, 5) << endl;
    cout << "Range sum from index (0 to 3): " << rangeSum(c_arr, 0, 3) << endl;
    cout << "Range sum from index (4 to 7): " << rangeSum(c_arr, 4, 7) << endl;
}

ผลลัพธ์

Range sum from index (2 to 5): 128
Range sum from index (0 to 3): 49
Range sum from index (4 to 7): 176