ต้นไม้ส่วน และ ต้นไม้ฟินวิก (Binary Indexed Tree, BIT) ตอบคำถาม ช่วงการสอบถาม (เช่น ผลรวมมากกว่า [l, r]) และ การอัปเดตจุด ใน O(log n) เมื่อเทียบกับ O(n) สำหรับการสแกนแบบไร้เดียงสา หรือ O(n) อัปเดตสำหรับอาร์เรย์ผลรวมคำนำหน้า
ต้นไม้ส่วน และ ต้นไม้ฟินวิก (Binary Indexed Tree, BIT) ตอบคำถาม ช่วงการสอบถาม (เช่น ผลรวมมากกว่า [l, r]) และ การอัปเดตจุด ใน O(log n) เมื่อเทียบกับ O(n) สำหรับการสแกนแบบไร้เดียงสา หรือ O(n) อัปเดตสำหรับอาร์เรย์ผลรวมคำนำหน้า
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)
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) และด้วยการแพร่กระจายแบบเกียจคร้าน ยังรองรับ การอัปเดตช่วง ด้วย
[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) |
| การดำเนินการ | ผลรวม (กลับด้านได้) | การดำเนินการเชื่อมโยงใด ๆ |
| การอัปเดตช่วง | ยากกว่า | ง่าย (การแพร่กระจายแบบเกียจคร้าน) |
| ขนาดโค้ด | เล็ก | ใหญ่กว่า |
โครงสร้างเหล่านี้ทำให้ "อัปเดตค่า จากนั้นสอบถามการรวมทั่วช่วง" เร็วขึ้น — สำคัญสำหรับการเขียนโปรแกรมแบบแข่งขัน หน้าต่างการวิเคราะห์ และปัญหาช่วง
การเลือกระหว่างพวกเขานั้นประกอบด้วยการแลกเปลี่ยน: ต้นไม้ฟินวิกมีขนาดเล็กและเร็วสำหรับผลรวม ขณะที่ต้นไม้ส่วนมีความยืดหยุ่นมากขึ้นสำหรับภาระงานการอัปเดตช่วง/นาที/สูงสุด