home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

Segment Trees ในโครงสร้างข้อมูล

โจทย์ที่ Segment Tree แก้

มี Array arr[0,...,n-1] ต้องการรองรับ 2 Operation:

  • Query: หาผลรวม Index l ถึง r (0 ≤ l ≤ r ≤ n-1)
  • Update: เปลี่ยนค่า arr[i] = x (0 ≤ i ≤ n-1)

Segment Tree Representation

  • Leaf Nodes = องค์ประกอบของ Array เดิม
  • Internal Nodes = ผลรวมของ Leaves ใต้โหนดนั้น (Merge Operation)

ตัวอย่าง

Array: [1, 3, 5, 7, 9, 11] Segment Tree:

Segment Trees ในโครงสร้างข้อมูล

Query และ Update ใช้เวลา O(log n)