เราต้องคำนวณผลรวมขององค์ประกอบจากดัชนี i ถึงดัชนี j คำสั่ง (queries) ที่ประกอบด้วยค่า i และ j จะถูก執行หลายครั้ง
Input: arr[] = {5, 6, 3, 4, 1}, i = 1, j = 3
Output: 13
คำอธิบาย
6 + 3 + 4 = 13
sum[] = {5, 6+5, 3+6+5, 4+3+6+5, 1+4+3+6+5}
sum[] = {5, 11, 14, 18, 19}
sum[j] - sum[i-1] = sum[3] - sum[0] = 18 - 5 = 13
ตรรกะพื้นฐานคือเริ่มลูปจากดัชนี i ถึง j และบวกองค์ประกอบระหว่างดัชนีเหล่านั้น แต่เราไม่สามารถเก็บในตัวแปรเพิ่มได้ ดังนั้นเราจะใช้อาร์เรย์อีกอันหนึ่งที่เราบวกองค์ประก้องอาร์เรย์กับองค์ประกอบสุดท้ายของอาร์เรย์ใหม่ไปเรื่อยๆ และจากดัชนี j เราจะลบค่าดัชนี i-1
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
int rangeSum(int i, int j, int sum[]) {
if (i == 0)
return sum[j];
return sum[j] - sum[i - 1];
}
int main() {
int arr[] = {5, 6, 3, 4, 1};
int n = 5;
int sum[5];
sum[0] = arr[0];
for (int i = 1; i < n; i++) {
sum[i] = arr[i] + sum[i - 1];
}
cout << rangeSum(1, 3, sum) << endl;
return 0;
}
ผลลัพธ์
13
