ต้นไม้ส่วนและต้นไม้ฟินวิก (BIT) รองรับการสอบถามช่วงอย่างรวดเร็วได้อย่างไร

Question

Accepted Answer

**ต้นไม้ส่วน** และ **ต้นไม้ฟินวิก** (Binary Indexed Tree, BIT) ตอบคำถาม **ช่วงการสอบถาม** (เช่น ผลรวมมากกว่า `[l, r]`) และ **การอัปเดตจุด** ใน **O(log n)** เมื่อเทียบกับ O(n) สำหรับการสแกนแบบไร้เดียงสา หรือ O(n) อัปเดตสำหรับอาร์เรย์ผลรวมคำนำหน้า

## ปัญหาที่พวกเขาแก้ไข

```text
Array + many "sum of range [l,r]" and "update index i" calls:
  naive prefix sums: query O(1) but UPDATE is O(n)
  segment/Fenwick:   query O(log n) AND update O(log n)
```

## ต้นไม้ฟินวิก (BIT) — กระชับและประณีต

```python
class Fenwick:
    def __init__(self, n):
        self.t = [0]*(n+1)
    def update(self, i, delta):        # O(log n)
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)              # jump to next responsible node
    def prefix(self, i):               # sum of [0..i], O(log n)
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l-1)
```

## ต้นไม้ส่วน — ทั่วไปมากขึ้น

ต้นไม้ส่วนจัดเก็บค่ารวมต่อส่วนอาร์เรย์ในต้นไม้ไบนารี รองรับ **การดำเนินการเชื่อมโยงใด ๆ** (ผลรวม ขั้นต่ำ สูงสุด gcd) และด้วยการแพร่กระจายแบบเกียจคร้าน ยังรองรับ **การอัปเดตช่วง** ด้วย

```text
        [0..7] sum
       /          \
   [0..3]         [4..7]
   /    \         /    \
 [0..1][2..3]  [4..5][6..7]   ... down to single elements
```

## การเปรียบเทียบ

| | ฟินวิก (BIT) | ต้นไม้ส่วน |
|---|---|---|
| สอบถาม / อัปเดต | O(log n) | O(log n) |
| พื้นที่ | O(n) | O(2n) |
| การดำเนินการ | ผลรวม (กลับด้านได้) | การดำเนินการเชื่อมโยงใด ๆ |
| การอัปเดตช่วง | ยากกว่า | ง่าย (การแพร่กระจายแบบเกียจคร้าน) |
| ขนาดโค้ด | เล็ก | ใหญ่กว่า |

## เหตุใดจึงมีความสำคัญ

โครงสร้างเหล่านี้ทำให้ "อัปเดตค่า จากนั้นสอบถามการรวมทั่วช่วง" เร็วขึ้น — สำคัญสำหรับการเขียนโปรแกรมแบบแข่งขัน หน้าต่างการวิเคราะห์ และปัญหาช่วง

การเลือกระหว่างพวกเขานั้นประกอบด้วยการแลกเปลี่ยน: ต้นไม้ฟินวิกมีขนาดเล็กและเร็วสำหรับผลรวม ขณะที่ต้นไม้ส่วนมีความยืดหยุ่นมากขึ้นสำหรับภาระงานการอัปเดตช่วง/นาที/สูงสุด

	ฟินวิก (BIT)	ต้นไม้ส่วน
สอบถาม / อัปเดต	O(log n)	O(log n)
พื้นที่	O(n)	O(2n)
การดำเนินการ	ผลรวม (กลับด้านได้)	การดำเนินการเชื่อมโยงใด ๆ
การอัปเดตช่วง	ยากกว่า	ง่าย (การแพร่กระจายแบบเกียจคร้าน)
ขนาดโค้ด	เล็ก	ใหญ่กว่า