ต้นไม้เซกเมนต์

ต้นไม้เซกเมนต์ หรือ Segment Tree เป็นโครงสร้างข้อมูลชนิดหนึ่งมีลักษณะเป็นต้นไม้ทวิภาค (Binary Tree)  ที่มีจุดเด่นในการเก็บ และ ถามข้อมูลเป็นช่วงมีขนาดคงที่ เมื่อโครงสร้างของข้อมูลถูกสร้างขึ้น โครงสร้างของไฟล์จะไม่สามารถเปลี่ยนแปลงได้ แต่สามารถปรับปรุงค่าของโหนดได้

  โดยรากของ Segment Tree แสดงถึง Array ทั้งหมด A[0 : N - 1] จากนั้นจะแบ่งออกเป็นสองส่วน โดยทางด้านซ้ายจะมีการเก็บข้อมูลในช่วง A[0 : (N-1)/2] และทางด้านชวาจะเก็บข้อมูลในช่วง A[((N-1)/2) + 1 : (N-1)]

ต้นไม้เซกเมนต์ มีการดำเนินการ 2 แบบ

 

Update

เพื่อปรับปรุงองค์ประกอบของ Array และ สะท้อนถึงการเปลี่ยนแปลงที่สอดคล้องกันในโครงสร้างของ Segment Tree สามารถดำเนินการได้โดย ค้นหาใบที่มีองค์ประกอบเพื่อการอัปเดต ซึ่งสามารถทำได้โดยไปที่ด้านซ้ายหรือด้านขวาของNode ตามช่วงเวลาที่มีองค์ประกอบ เมื่อพบใบแล้วจะมีการปรับปรุงเปลี่ยนแปลงที่สอดคล้องกันในเส้นทางจากใบนั้นไปยังราก ซึ่งผลรวมของธาตุจากดัชนี l ถึง r โดยที่ 0 <= l <= r <= n-1

แบบสอบถาม

ในการดำเนินการนี้เราสามารถสืบค้นในช่วงเวลาหรือกลุ่มและส่งคืนคำตอบให้กับปัญหา (เช่น หาค่า น้อยที่สุด / สูงสุด / บวกในส่วนใดส่วนหนึ่ง) และสามารถหาค่าได้อย่างมีประสิทธิภาพจากการหาค่าต่ำสุดและมากสุดจากดัชนี qs (เริ่มต้นแบบสอบถาม) เพื่อqe (สิ้นสุดแบบสอบถาม) ที่0 <=  qs <= qe <= n-1

ตัวอย่างของ Segment Tree

เป็นตัวอย่างต้นไม้เซ็กเม้นต์ที่มีขนาด 7

ตัวอย่างของ Segment Tree (ค่าที่น้อยที่สุดในช่วงที่กำหนด)

เป็นตัวอย่างของ Segment Tree (ค่าที่น้อยที่สุดในช่วงที่กำหนด)

ช่วงของค่าต่ำสุดที่กำหนด

1. ถ้าช่วงของโหนดอยู่ภายใน qs และ q => ค่าที่ส่งคืนในโหนด

2.ถ้าช่วงโหนดอยู่นอก qs และ qe => infinite

3.นอกเหนือที่กล่าวมา => (ลูกซ้ายของโหนด, qs, qe), (ลูกขวาของโหนด, qs, qe)

ตัวอย่างของ Segment Tree (หาผลบวกของช่วงที่กำหนด)

เป็นตัวอย่างของ Segment Tree (หาผลบวกของช่วงที่กำหนด)

ช่วงผลรวมที่กำหนด

1. ถ้าช่วงของโหนดอยู่ภายใน l และ r  => ค่าที่ส่งคืนในโหนด

2.ถ้าช่วงโหนดอยู่นอก l และ r => 0

3.นอกเหนือที่กล่าวมา => (ลูกซ้ายของโหนด, l, r) + (ลูกขวาของโหนด, l, r)

ความซับซ้อนของเวลา

1. แบบสอบถาม

- เวลาสำหรับการก่อสร้างต้นไม้คือ O (n) มีโหนด 2n-1 ทั้งหมดและค่าของโหนดทุกตัวจะคำนวณเพียงครั้งเดียวในการสร้างโครงสร้าง

- ความซับซ้อนของเวลาในการค้นหาคือ O (log n) เราจะประมวลผลได้มากที่สุด 2 โหนดในทุกระดับและจำนวนของระดับคือ O (log n)

2. Update

- เวลาสำหรับการก่อสร้างต้นไม้คือ O(n) มีโหนด 2n-1 ทั้งหมดและค่าของโหนดทุกตัวจะคำนวณเพียงครั้งเดียวในการสร้างโครงสร้าง

- ความซับซ้อนของเวลาในการค้นหาคือ O(log n) ในการค้นหาผลรวมเราประมวลผลได้มากที่สุดสี่โหนดในทุกระดับและจำนวนของระดับคือ O(log n)

- ความซับซ้อนของเวลาในการอัปเดตก็คือ O(log n) เราจะประมวลผลโหนดหนึ่งที่ทุกระดับและจำนวนของระดับคือ O (log n)

Code การเพิ่ม

def _add(self, start, end, weight, in_start, in_end):
        key = (in_start, in_end)
        if in_start == in_end:
            self.max_value[key] += weight
            self.sum_value[key] += weight
            self.len_value[key] = 1 if self.sum_value[key] > 0 else 0
            return

        mid = in_start + int((in_end - in_start) / 2)
        if mid >= end:
            self._add(start, end, weight, in_start, mid)
        elif mid+1 <= start:
            self._add(start, end, weight, mid+1, in_end)
        else:
            self._add(start, mid, weight, in_start, mid)
            self._add(mid+1, end, weight, mid+1, in_end)
        self.max_value[key] = max(self.max_value[(in_start, mid)], self.max_value[(mid+1, in_end)])
        self.sum_value[key] = self.sum_value[(in_start, mid)] + self.sum_value[(mid+1, in_end)]
        self.len_value[key] = self.len_value[(in_start, mid)] + self.len_value[(mid+1, in_end)]

Code ค่าmax

def _query_max(self, start, end, in_start, in_end):
        if start == in_start and end == in_end:
            ans = self.max_value[(start, end)]
        else:
            mid = in_start + int((in_end - in_start) / 2)
            if mid >= end:
                ans = self._query_max(start, end, in_start, mid)
            elif mid+1 <= start:
                ans = self._query_max(start, end, mid+1, in_end)
            else:
                ans = max(self._query_max(start, mid, in_start, mid),
                        self._query_max(mid+1, end, mid+1, in_end))
    
        return ans

อ้างอิง

leonsim segmenttree ค้นหาเมื่อ 29 เมษายน 2561

geeksforgeeks Segment Tree | Set 1 (Sum of given range) ค้นหาเมื่อ 29 เมษายน 2561

geeksforgeeks Segment Tree | Set 2 (Range Minimum Query) ค้นหาเมื่อ 29 เมษายน 2561

Akash Sharma Segment Trees ค้นหาเมื่อ30 เมษายน