โปรแกรม C ++ สำหรับการสืบค้นผลรวมของช่วงโดยไม่มีการอัพเดต?

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

อัลกอริทึม

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];
}
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