Python - Prefix Sum List (ผลรวมสะสม)

ลิสต์เป็นคอลเลกชันที่มีลำดับและเปลี่ยนแปลงได้ เขียนด้วยวงเล็บเหลี่ยม เข้าถึงได้โดยดัชนี โดย -1 คือตัวสุดท้าย สามารถ slice ได้เพื่อดึงช่วงข้อมูล

ตัวอย่างโค้ด

ใช้ List Comprehension + sum() + Slicing

# เริ่มต้นลิสต์
test_list = [3, 4, 1, 7, 9, 1]
print("The original list :", str(test_list))

# Prefix sum list
res = [sum(test_list[: i + 1]) for i in range(len(test_list))]

print("The prefix sum list is :", str(res))

ผลลัพธ์

The original list : [3, 4, 1, 7, 9, 1]
The prefix sum list is : [3, 7, 8, 15, 24, 25]

วิธีที่มีประสิทธิภาพมากกว่า (O(n) แทน O(n²))

วิธีเดิมใช้ sum() ในลูป ทำให้เป็น O(n²) สำหรับลิสต์ใหญ่ควรใช้วิธีสะสม:

1. ใช้ Loop สะสม (แนะนำ)

def prefix_sum(lst):
    result = []
    total = 0
    for x in lst:
        total += x
        result.append(total)
    return result

test_list = [3, 4, 1, 7, 9, 1]
print(prefix_sum(test_list))  # [3, 7, 8, 15, 24, 25]

2. ใช้ itertools.accumulate (Python 3.2+)

from itertools import accumulate

test_list = [3, 4, 1, 7, 9, 1]
res = list(accumulate(test_list))
print(res)  # [3, 7, 8, 15, 24, 25]

3. ใช้ NumPy (สำหรับอาร์เรย์ใหญ่)

import numpy as np

test_list = [3, 4, 1, 7, 9, 1]
res = np.cumsum(test_list)
print(res)  # [ 3  7  8 15 24 25]

เปรียบเทียบประสิทธิภาพ

การประยุกต์ใช้ Prefix Sum

• Range Sum Query: ผลรวมช่วง [l, r] = prefix[r] - prefix[l-1] (O(1))
• Subarray sum equals K
• Equilibrium index
• Running total / Cumulative statistics

ตัวอย่าง Range Sum Query

def range_sum(prefix, l, r):
    """ผลรวมช่วง l ถึง r (0-indexed, inclusive)"""
    if l == 0:
        return prefix[r]
    return prefix[r] - prefix[l - 1]

arr = [3, 4, 1, 7, 9, 1]
prefix = list(accumulate(arr))
print(range_sum(prefix, 1, 3))  # 4+1+7 = 12
print(range_sum(prefix, 0, 5))  # 25 (ทั้งหมด)