線段樹入門小結QUE：線段樹？SUM：線段樹和樹狀數組的聯系與差別？

稱謂：

從劉汝佳的書中得知，“這種資料結構在學術界沒有統一的術語，但線段樹是最常見的叫法。其他叫法包括區間樹（interval

tree）、範圍樹（range

tree）等，但這些屬于在特定的場合（如計算幾何）中有着特殊的意義”。怎麼叫看讀者的心情，以下統一用線段樹稱呼。

先來作一些了解：

線段樹是一棵二叉樹，它的左右兒子也都是一棵線段樹。（定義）

線段樹也叫區間樹，為什麼叫它區間樹呢？因為線段樹是一種基于區間的資料結構。

線段樹的每個節點代表一個區間

[l,r]，其中存儲的是這個區間的特定值。

例如rmq（range minimum/maximum

query，範圍最大/最小值）問題，給出n個元素的數組，查詢任意區間内的元素最大/最小值。

這個問題就是基于區間查詢的，需要用到線段樹，而它節點中存儲的特定值就是所代表區間的最大/最小值。

某個節點代表區間 [l,r]，其兩個兒子節點代表區間分别為

[l,mid],[mid+1,r]（ mid = (l+r)/2 ）。

線段樹的操作：

1、點修改

在[l,r]中修改[ll,rr](ll=rr)的時候有兩種情況。

第一種，[ll,rr]被[l,mid]包含，此時直接在[l,mid]中修改[ll,rr]

第二種，[ll,rr]被[mid+1,r]包含，此時直接在[mid+1,r]中修改[ll,rr]（同理）

然後遞歸更新父親。

不用考慮被截斷（因為隻是一個點）。

2、區間修改

在[l,r]中修改[ll,rr](ll<rr)的時候有三種情況。

第三種，較複雜的一種，[ll,rr]被mid從中截斷，此時在[l,mid]中修改[ll,mid]，在[mid+1,r]中修改[mid+1,rr]，然後将兩個查詢得到的結果進行update，遞歸更新父親。

這樣便處理完了修改。

線段樹的應用：

rmq問題，存儲值，優化dp。

freecode :