數據流與區間問題：概覽

典型業務場景

處理隨時間變化的數據或需要複雜的區間查詢是高性能系統的核心需求：

• 金融交易： 「上午 10:00 到下午 2:00 之間的最高股價是多少？」 (RMQ - 區間最值查詢)。
• 廣告技術： 在數百萬個特定時間段內計算廣告系列總消耗。
• 遊戲開發： 即時排行榜，玩家的分數每秒都在變化（動態更新）。
• 系統監控： 在滑動窗口中尋找過去 10,000 個請求的中位延遲。
• 物流系統： 確定路線中特定地理分段的總負載。

選型框架：怎麼選？

1. 數據是靜態的還是動態的？
   • 靜態（無更新）： 使用 稀疏表 (Sparse Table) 實現 $O(1)$ 的區間查詢。
   • 動態（頻繁更新）： 使用 線段樹 (Segment Tree) 或 樹狀陣列 (Fenwick Tree)。
2. 查詢類型是什麼？
   • 區間和： 樹狀陣列 記憶體最省，實現最簡單。
   • 複雜區間操作 (最值/公約數)： 線段樹 是萬能解法。
3. 是否是持續的流數據？
   • 是： 使用 滑動窗口 (單調隊列) 或 對頂堆 來計算中位數等即時指標。

常見演算法速覽

• 6.1 線段樹： 瑞士軍刀。支援 $O(\log N)$ 的區間修改和區間查詢。
• 6.2 樹狀陣列 (BIT)： 輕量級結構，專攻前綴和與點更新。
• 6.3 稀疏表： 透過預計算，在常數 $O(1)$ 時間內回答區間最值查詢。
• 6.4 單調隊列： 高效尋找大小為 $K$ 的滑動窗口內的最大/最小值。
• 6.5 對頂堆： 在即時數據流中尋找中位數的標準模式。

選型對比速查表

一句話心法

「區間結構透過少量的預處理和記憶體，將低效的線性掃描轉化為閃電般的對數或常數級查找。」