คำอธิบายปัญหา
สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม เราต้องหาผลรวมขององค์ประกอบที่อยู่ระหว่างดัชนี i ถึง j มี 2 สิ่งต้องระวัง: อาร์เรย์จะเป็น immutable (ไม่เปลี่ยนแปลง) ดังนั้นองค์ประกอบจะไม่ถูกแก้ไข และจะมีหลายคิวรี่แบบนี้ ดังนั้นเราต้องคำนึงถึงเวลาการทำงานสำหรับจำนวนคิวรี่มาก สมมติอาร์เรย์คือ 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
