การหาผลรวมของ 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:
- remixman's blog
- Log in to post comments