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

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

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

12 5 10 3 25 6 11 8

ถ้าหากคำนวณตามปกติก็จะได้เป็นการวนลูปบวกไปทีละตัว ตั้งแต่ช่องที่ 2 จนถึง 6 หรือถ้ามองในรูปทั่วไปของปัญหาก็คือ วนลูปแล้วบวกค่าของสมาชิกตัวที่ $i$ จนถึงตัวที่ $j$ ซึ่งจะได้ว่าเวลาในการทำงานโดยเฉลี่ยแต่ละครั้งเป็น $O(n)$ เวลาที่ได้อาจจะไม่แย่เท่าไหร่ แต่ถ้าเกิดหาต้องการหาผลรวมของ sub-array หลายช่วงและหลายครั้งก็น่าจะช้าพอดู เราสามารถลดเวลาการหาผลรวมลงได้หรือไม่?

เพื่อให้ง่ายต่อการเรียก ต่อจากนี้จะขอเรียกการหาผลรวมของ sub-array แต่ละครั้งว่า query ดังนั้นคำถามคือทำยังไงให้ query แต่ละครั้งทำงานได้เร็วขึ้น

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

12 17 27 30 55 61 72 80

จากข้อมูลตัวอย่างดังกล่าวข้อมูลในช่องที่ 4 ของอาร์เรย์ $S$ ก็จะเป็นผลรวมของ $A$ ตั้งแต่ 1 ถึง 4 ซึ่งมีค่าเท่ากับ 12 +5 + 10 + 3 = 30 หรือว่าในช่องที่ 6 ก็จะเป็นผลรวมของอาร์เรย์ $A$ ตั้งแต่ 1 ถึง 6 ซึ่งมีค่าเท่ากับ 12 + 5 + 10 + 3 + 25 + 6 = 61

ตัวอาร์เรย์ $S$ ที่เก็บข้อมูลผลรวมของ $A$ นั้นเราจะเรียกว่าเป็น Prefix sum array ซึ่งการที่เรามี Prefix sum array จะทำให้เราสามารถ query ผลรวมของ sub-array ได้เร็วขึ้น เช่นถ้าต้องการผลรวมของ $A$ ตั้งแต่ 3 ถึง 6 ก็เพียงแค่หาจาก $S[6] - S[2]$ (เนื่องจาก $S[6]$ คือผลรวมจนถึงช่องที่ 6 และ $S[2]$ คือผลรวมจนถึงช่องที่ 3 ดังนั้นเมื่อลบกันก็จะได้ค่าที่ต้องการพอดี) สำหรับรูปทั่วไปก็คือ ค่าผลรวมของ sub-array ตั้งแต่ช่องที่ $i$ จนถึง $j$ จะหาได้จาก $S[j] - S[i-1]$ ยกเว้นกรณีที่ $i = 1$ ก็สามารถใช้ค่าของ $S[j]$ ได้เลย วิธีนี้สามารถตอบ query ได้อย่างรวดเร็วใน constant time เนื่องจากใช้เพียงการลบข้อมูลเพียงครั้งเดียวเท่านั้น

ในส่วนของการสร้าง Prefix sum array นั้นทำได้ไม่ยาก และทำได้ในเวลา $O(n)$ นั่นคือ $S[i]$ หาได้จากการนำช่องก่อนหน้า ($S[i-1]$) มาบวกกับ $A[i]$ เนื่องจากค่าของช่องก่อนหน้าก็คือผลรวมของ $A[1]$ จนถึง $A[n]$ ซึ่งเขียนเป็นโค้ดสำหรับสร้าง Prefix sum array $S$ ได้ดังนี้

int S[n];
S[0] = A[0];
for (int i = 1; i < n; ++i)
    S[i] = S[i-1] + A[i];

จะเห็นว่าโค้ดเขียนได้ง่ายมาก (ในตัวอย่าง index ของอาร์เรย์จะเริ่มที่ 1 แต่ในโค้ดขอเริ่มที่ 0 นะครับ) ซึ่งโดยสรุปแล้วก็คือวิธีนี้จะช่วยให้เราหาผลรวมของ sub-array ได้เร็วขึ้น แต่จะต้องแลกกับการประมวลผลข้อมูลก่อนเพื่อสร้าง Prefix sum array

โดยสรุปแล้วจะได้อะไรประมาณนี้ครับ

  • Memory : $O(n)$ - สร้างอาร์เรย์ใหม่ขนาดเท่าอาร์เรย์เดิม
  • Preprocessing time : $O(n)$ - ต้องคำนวณก่อน โดยคำนวณเท่ากับขนาดอาร์เรย์เดิม
  • Query time : $O(1)$ - ทุกครั้งที่ query จะตอบได้ในทันที

Taxonomy upgrade extras: