Prefix Sum — พื้นฐาน & แนวคิด

Prefix Sum (ผลรวมสะสม) เป็นเทคนิคง่าย ๆ แต่ทรงพลังมาก ไอเดียคือ ถ้าเราถูกถามผลรวมของ range (ช่วง) ต่าง ๆ ใน array (ลิสต์) บ่อย ๆ แทนที่จะบวกใหม่ทุกครั้ง เรา precompute (เตรียมล่วงหน้า) prefix sum ไว้ แล้วตอบคำถามได้ทันทีในเวลาคงที่ นอกจากนี้ตัว prefix sum เองก็มีประโยชน์ในโจทย์ที่ต้องรู้ค่าสะสม ณ แต่ละจุด เช่น altitude (ระดับความสูง) ที่ไต่ขึ้นไปได้ หรือหา pivot (จุดสมดุล) ของ array

แนวคิดของหัวข้อนี้

สมมติเรามี array nums แล้วอยากรู้ผลรวมของ range nums[i..j] (รวมทั้งสองปลาย) ถ้าถามครั้งเดียวก็บวกตรง ๆ ได้ แต่ถ้าถูกถามหลาย ๆ range การบวกใหม่ทุกครั้งจะเสียเวลา O(n) ต่อ query (คำถาม) รวมแล้วช้า

ทริกคือสร้าง array prefix ที่เก็บผลรวมสะสมตั้งแต่ต้นจนถึงแต่ละ index (ตำแหน่ง) โดยนิยมทำให้ prefix ยาวกว่า nums หนึ่งช่อง (มีช่อง 0 นำหน้า) เพื่อให้สูตรสวย: prefix[k] = ผลรวมของ nums[0..k-1]

ทำไมมันเร็วขึ้น? เพราะเราจ่ายเวลา O(n) แค่ครั้งเดียวตอน build (สร้าง) prefix จากนั้นทุก range query ตอบได้ในเวลา O(1) ด้วยการลบกันแค่ครั้งเดียว ผลรวม range = ผลรวมสะสมถึงปลายขวา ลบ ผลรวมสะสมก่อนถึงปลายซ้าย

nums = [3, 1, 4, 1, 5]

# สร้างผลรวมสะสม โดยให้ prefix[0] = 0 นำหน้า
prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
    prefix[i + 1] = prefix[i] + nums[i]

# prefix = [0, 3, 4, 8, 9, 14]

# ผลรวมของช่วง nums[i..j] (รวมสองปลาย) = prefix[j + 1] - prefix[i]
# เช่น ผลรวมของ nums[1..3] = 1 + 4 + 1 = 6
i, j = 1, 3
print(prefix[j + 1] - prefix[i])  # 6