Prefix sum

การหาผลรวมของ sub-array ในเวลา constant time

การหาผลรวมของ sub-array เป็นปัญหาพื้นฐานอันหนึ่งที่พบเจอได้บ่อย ลักษณะของปัญหาคือ ให้อาร์เรย์ $A$ ที่มีขนาด $n$ มา จากนั้นถามว่าผลรวมของ sub-array ตั้งแต่สมาชิกตัวที่ $i$ จนถึงตัวที่ $j$ มีค่าเป็นเท่าไหร่

ลองดูตัวอย่างของปัญหาเพื่อให้ชัดเจนขึ้นนะครับ ให้อาร์เรย์ $A$ มีขนาด 8 และมีสมาชิกตามรูป ถามว่าผลรวมของสมาชิกตัวที่ 2 ถึง 6 มีค่าเป็นเท่าไหร่

Taxonomy upgrade extras: 

Subscribe to RSS - Prefix sum