สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม เราต้องหาผลรวมขององค์ประกอบที่มีอยู่จากดัชนี i ถึง j สองสิ่งที่เราต้องจำไว้คืออาร์เรย์จะไม่เปลี่ยนรูป ดังนั้นองค์ประกอบจะไม่ถูกแก้ไข และจะมีข้อความค้นหาดังกล่าวหลายรายการ ดังนั้นเราจึงต้องคำนึงถึงเวลาดำเนินการสำหรับข้อความค้นหาจำนวนมาก สมมติว่าอาร์เรย์เป็นเหมือน A =[5, 8, 3, 6, 1, 2, 5] ดังนั้นหากการสืบค้นคือ (A, 0, 3) ก็จะเป็น 5 + 8 + 3 + 6 =22
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- รับหนึ่งอาร์เรย์ B. B[i] จะเก็บผลรวมขององค์ประกอบตั้งแต่ 0 ถึง i
- สำหรับแบบสอบถามดำเนินการ B[j] – B[i – 1]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class NumArray {
public:
vector <int> pre;
NumArray(vector<int>& nums) {
pre.clear();
int n = nums.size();
pre.resize(n);
for(int i = 0; i < n; i++){
if(i == 0)pre[0] = nums[0];
else
pre[i] = pre[i - 1] + nums[i];
}
}
int sumRange(int i, int j) {
if(i == 0)return pre[j];
return pre[j] - pre[i - 1];
}
};
main(){
vector<int> v = {5,8,3,6,1,2,5};
NumArray na(v);
cout<<na.sumRange(0,2)<<endl;
cout<<na.sumRange(2,5)<<endl;
cout<<na.sumRange(0,5)<<endl;
} อินพุต
Initialize it with [5,8,3,6,1,2,5] Call sumRange(0,2) sumRange(2,5) sumRange(0,5)
ผลลัพธ์
16 12 25
