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

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

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

## การดำเนินการ
### Update
เพื่อปรับปรุงองค์ประกอบของ Array และ สะท้อนถึงการเปลี่ยนแปลงที่สอดคล้องกันในโครงสร้างของ Segment Tree สามารถดำเนินการได้โดย ค้นหาใบที่มีองค์ประกอบเพื่อการอัปเดต ซึ่งสามารถทำได้โดยไปที่ด้านซ้ายหรือด้านขวาของ Node ตามช่วงเวลาที่มีองค์ประกอบ เมื่อพบใบแล้วจะมีการปรับปรุงเปลี่ยนแปลงที่สอดคล้องกันในเส้นทางจากใบนั้นไปยังราก ซึ่งผลรวมของธาตุจากดัชนี l ถึง r โดยที่ 0  ค่าที่ส่งคืนในโหนด
#ถ้าช่วงโหนดอยู่นอก qs และ qe => infinite
#นอกเหนือที่กล่าวมา => (ลูกซ้ายของโหนด, qs, qe), (ลูกขวาของโหนด, qs, qe)  

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

**ช่วงผลรวมที่กำหนด**
#ถ้าช่วงของโหนดอยู่ภายใน l และ r => ค่าที่ส่งคืนในโหนด
#ถ้าช่วงโหนดอยู่นอก l และ r => 0
#นอกเหนือที่กล่าวมา => (ลูกซ้ายของโหนด, 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 การเพิ่ม

```python3
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 ค่ามากที่สุด

```python3
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 เมษายน

หมวดหมู่:ต้นไม้ทวิภาค
หมวดหมู่:โครงสร้างข้อมูลกราฟิกคอมพิวเตอร์