ผลรวมคำนำหน้าคืออะไร และมันเร่งความเร็วการค้นหาช่วงได้อย่างไร

Question

IT Interview Practice · Accepted Answer

อาร์เรย์ **ผลรวมคำนำหน้า** จัดเก็บผลรวมสะสม เพื่อให้ **ผลรวมช่วง** ใดๆ ตอบได้ใน **O(1)** หลังจากการประมวลผลก่อนล่วง O(n) — แทนที่จะเป็น O(n) ต่อการค้นหา

## แนวคิด

ให้ `prefix[i]` เป็นผลรวมของ `i` องค์ประกอบแรก จากนั้นผลรวมของ `arr[l..r]` คือ `prefix[r+1] - prefix[l]`

## ตัวอย่าง

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x   # running total
    return prefix

def range_sum(prefix, l, r):            # inclusive l..r
    return prefix[r + 1] - prefix[l]    # O(1)

p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3)                      # 4+1+3 -> 8
```

## การติดตาม

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## ความซับซ้อน

- **สร้าง:** O(n). **ค้นหา:** O(1). **พื้นที่:** O(n)

## เมื่อใช้ / ข้อเสี่ยง

เหมาะสำหรับ **หลายการค้นหาผลรวมช่วง** บนข้อมูลแบบสถิต รูปแบบต่างๆ: ผลรวมคำนำหน้า 2D สำหรับผลรวมเมทริกซ์ย่อย XOR คำนำหน้า และอาร์เรย์ความแตกต่างสำหรับการอัปเดตช่วง หากอาร์เรย์มีการเปลี่ยนแปลงบ่อย ให้ใช้ Fenwick/segment tree แทน ระวังค่า offset ของดัชนี (ขนาด n+1)

## ทำไมถึงสำคัญ

ผลรวมคำนำหน้าเปลี่ยนการค้นหาช่วง O(n) ที่ซ้ำๆ เป็นการค้นหา O(1) — ชัยชนะครั้งใหญ่เมื่อการค้นหามีความถี่สูง

รูปแบบการคำนวณล่วงหน้าครั้งเดียวและตอบรับอย่างรวดเร็ว ทั่วไปไปยังหลายงานการประมวลผลข้อมูล

เป็นเสาหลักของการเขียนโปรแกรมเชิงการแข่งขันและบล็อกการสร้างทั่วไปในการวิเคราะห์

แนวคิด

ตัวอย่าง

การติดตาม

ความซับซ้อน

เมื่อใช้ / ข้อเสี่ยง

ทำไมถึงสำคัญ

คำถามที่เกี่ยวข้อง