🌳 線段樹 （Segment Tree）：玩轉區間作的終極利器

你好，未來的算法大師！

想象一下，你正在處理一個巨大的數據集，比如某個電商網站一整天的用戶點擊流。老板突然問你：“下午2點到3點之間，我們的總點擊量是多少？” 幾分鐘后，他又問：“把10點到11點之間的數據，因為系統故障，全部乘以0.5，然后再告訴我下午的總點擊量。”

如果用普通的數組，每次查詢都需要遍歷，每次修改更是災難。面對這種需求，我們該怎么辦？頻繁的區間查詢和區間修改

答案，就是我們今天的主角——。線段樹 （Segment Tree）

這篇文章將帶你：

1. 直擊痛點：理解普通數組在區間問題上的局限性。

2. 掌握神器：了解線段樹如何用的時間復雜度解決這些問題。O（對數 N）

3. 展望進階：一窺線段樹的“動態開點”和“懶更新”等高級玩法。

準備好了嗎？讓我們開始構建這棵神奇的“信息之樹”。

😫 The Pain： 區間問題的困境

在深入線段樹之前，我們先感受一下“沒有線段樹”時的痛苦。

假設我們有一個數組，需要頻繁查詢任意區間的最小值。一個常見的優化思路是。比如，我們可以創建一個數組，其中存儲這個后綴區間的最小值。數字預計算后綴最小后綴Min[i]nums[i：]

      # 預計算后綴最小值的示例
nums = [3, 1, 4, 2]
# suffixMin[i] 表示 nums[i..] 中的最小值
suffixMin = [0] * len(nums)  ：創建一個和 nums 長度相同的數組，用來存每個位置的「后綴最小值」# 從后往前計算
suffixMin[len(nums) - 1] = nums[len(nums) - 1]  作用：最后一個人的后綴只有自己，所以他的「后綴最小值」就是自己的身高。
for i in range(len(nums) - 2, -1, -1):suffixMin[i] = min(nums[i], suffixMin[i + 1])# suffixMin 會是 [1, 1, 2, 2]
print(suffixMin)# 查詢 nums[1..] 的最小值
# O(1) 時間查詢，非常快！
print(suffixMin[1]) # 輸出 1

這種“前綴和/后綴和”思想很棒，查詢效率是，但它有一個：O（1）致命弱點

無法應對動態修改！

一旦中的某個元素改變，比如變了，那么和都需要重新計算。如果數組很大，一次修改可能導致的更新成本，這在高性能場景下是不可接受的。數字數字[1]后綴Min[0]后綴Min[1]O（N）

痛點總結：

• 靜態數組：區間查詢慢 （），單點更新快 （）。O（N）O（1）

• 預計算數組：特定區間查詢快 （），但更新慢 （）。O（1）O（N）

我們需要一個既能快速查詢，又能快速更新的數據結構。于是，線段樹應運而生。

? The Magic： 線段樹的核心能力

一句話定義：線段樹是一種，它將一個區間分解成若干個子區間，每個節點代表一個區間的“聚合信息”（如和、最值等），從而實現快速的區間操作。平衡二叉樹

核心 API 概覽 （?）

一個基礎的線段樹通常提供以下接口：

      from typing import Callableclass SegmentTree:def __init__(self, nums: list[int], merge: Callable[[int, int], int]):"""構造函數，基于一個數組初始化線段樹。時間復雜度: O(N)Args:nums (list[int]): 原始數組。merge (Callable): 一個函數，定義了如何合并兩個子區間的信息。例如，求和是 lambda a, b: a + b，求最小值是 lambda a, b: min(a, b)。"""passdef query(self, i: int, j: int) -> int:"""查詢閉區間 [i, j] 的聚合值。時間復雜度: O(log N)"""passdef update(self, i: int, val: int):"""將數組中索引 i 的值更新為 val。時間復雜度: O(log N)"""pass

為什么是 ？O(log N)

1. 樹高是 O(log N)：線段樹在構建時，總是從中間分割區間，這保證了它是一棵的二叉樹。樹的高度決定了操作的上限。高度平衡

2. query 的路徑：查詢一個區間 時，這個大區間可以被巧妙地拆分成樹上 個節點所代表的小區間。我們只需將這些節點的信息合并即可。[i, j]O(log N)

3. update 的路徑：更新一個葉子節點時，我們只需要沿著從該葉子到根節點的唯一路徑，更新路徑上的所有父節點。這條路徑的長度就是樹的高度，即 。O(log N)

🚀 The Evolution: 線段樹的進階形態

基礎線段樹已經很強大了，但在更復雜的場景下，它還有一些更酷的變體。

懶更新 (Lazy Propagation) 舉例:
想象一下，要把 [0, 100] 這個區間的所有數都加上 5。我們不必真的去更新 101 個葉子節點。我們只需在代表 的那個根節點上貼一個標簽：“嘿，我這里的所有子孫后代都要加 5”。[0, 100]

只有當查詢操作需要深入到這個節點的子區間時，我們才把這個“懶任務”向下傳遞一層。這個技巧極大地提升了區間更新的效率，使其也能達到 。O(log N)

🧠 學習成果檢驗 (必會)

現在，檢驗一下你是否掌握了線段樹的核心思想。請嘗試回答以下問題：

問題 1：
為什么說線段樹是一種“空間換時間”的數據結構？它比原始數組多占用了多少空間？

問題 2：
如果我想用線段樹來解決“查詢區間 內有多少個偶數”的問題，我應該如何定義 中的 函數和葉子節點的值？

比喻：分糖果統計
假設每個數字是一顆糖，偶數糖是粉色（值為 1），奇數糖是藍色（值為 0）。線段樹的任務是統計任意區間內的粉色糖數量。

具體做法：

1. 葉子節點：每個葉子對應一個數字，存 “1”（粉色）或 “0”（藍色）。
   • 比如數字4（偶數）→ 葉子存1；數字3（奇數）→ 葉子存0。
2. merge 函數：父節點把左右子節點的數加起來，就像把兩堆糖合起來數總數。
   • 左子樹有 2 顆粉色糖，右子樹有 1 顆→ 父節點存 3 顆。

舉個例子：
數組[2, 3, 4, 5]?→ 葉子節點是[1, 0, 1, 0]。

• 左子樹（前兩個數）的和是1+0=1（表示有 1 個偶數）。
• 右子樹（后兩個數）的和是1+0=1。
• 根節點的和是1+1=2，即整個數組有 2 個偶數。

問題 3：
一個朋友告訴你：“我可以用 個預計算的前綴和數組，在 時間內查詢任意區間的和，并且支持 的單點更新，這比線段樹的 查詢要快！” 他的說法在什么情況下可能是合理的，又在什么情況下線段樹是更優的選擇？NO(1)O(N)O(log N)