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

ต้นไม้เซกเมนต์ หรือ 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
ตัวอย่างของ Segment Tree (ค่าที่น้อยที่สุดในช่วงที่กำหนด)
ช่วงของค่าต่ำสุดที่กำหนด
1. ถ้าช่วงของโหนดอยู่ภายใน qs และ q => ค่าที่ส่งคืนในโหนด
2.ถ้าช่วงโหนดอยู่นอก qs และ qe => infinite
3.นอกเหนือที่กล่าวมา => (ลูกซ้ายของโหนด, qs, qe), (ลูกขวาของโหนด, qs, qe)
ตัวอย่างของ 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