---
tags: 基礎資料結構
title: 線段樹 (Segment Tree)
---

# 線段樹 (Segment Tree)
:::info
### 前言：
線段樹的功能很強大，可以支援各種區間操作
:::
:::success
## 區間查詢（以RMQ為例）：
- 相對ST表而言，這分法犧牲了查詢複雜度，但仍舊可以解決大部分區間查詢的問題
- 線段樹的常數有點大，請多多留意～

### 方法：
- 考慮把區間拆成 $O(logn)$ 個「不重疊的」區間
- 建表建成這樣（對於以下這些區間建立最大值）：
- 這麼一來，
- 建表複雜度：$O(n)$
- 查詢複雜度：$O(logn)$
:::
:::success
## 單點修改：
- 如果只有單點修改，很簡單
- 觀察一下上面的圖，如果我們要將點k做修改，會發現整棵樹包含到點k的區間只有$O(logn)$個，所以：
- 時間複雜度：$O(logn)$
## 區間修改（以 RMQ 為例）：
- 如果修改一個區間，最暴力的作法是把每個區間內的點做單點修改。
- 時間複雜度：$O(n)$
- 似乎有點太大！
- 沒關係，現在才是線段樹真正厲害的地方～～！
- 我們從區間查詢的方法，發現如果我們只修改至多這$O(logn)$個區間就好了～
- 時間複雜度：$O(logn)$
- **可是有些需要被修改的點就沒被改到阿！？沒關係，我們有懶人標記。**
### 懶人標記（lazy tag）
- 如果我們修改了一個點，並且那個點之後都*沒被查詢*，那不修改也沒差對吧（？）
- 所以我們只要記得這個區間有被修改過，並且查詢時，分別告訴左右子樹（如果有的話），你們也被修改了！
- 講的抽象，舉個例子：
- 你現在是小主管，總經理要發年終獎金給大家，並且拿一部分給你的老闆(Alien)，希望你的老闆(Bob)分配給你底下的成員。
- 有趣的事情來了：
1. 你的老闆(Bob)懶得發下去，就先自己獨吞了>\_\<
2. 總經理(Alien)也不是笨蛋，他要去檢查你有沒有拿到年終獎金。
3. 你的老闆(Bob)不得已，只好把獎金發給你們了
4. 於是你通過檢查了～
5. 這次換你懶得發下去，就先自己獨吞了>\_\<
6. 總經理(Alien)也不是笨蛋，他要去檢查你的下屬(Clinton)有沒有拿到年終獎金。
7. 你被迫將該給你下屬們的年終獎金發給它們
8. 於是你的下屬(Clinton)通過檢查了～
:::
:::info
### 題目：
- [模板 ZJ d539](https://zerojudge.tw/ShowProblem?problemid=d539)
- [變形題 POJ 3419](http://poj.org/problem?id=3419)
- [變形題 ZJ a164](https://zerojudge.tw/ShowProblem?problemid=a164)
- [挑戰題 SPOJ DQUERY](https://www.spoj.com/problems/DQUERY/)
:::