文章目錄

• 簡(jiǎn)介
• 最小線段樹
• 線段樹的構(gòu)建
• 線段樹的搜索
• 線段樹的更新
• 線段樹的復(fù)雜度

簡(jiǎn)介

什么是線段樹呢？線段樹是一種二叉搜索樹，與區(qū)間樹相似，它將一個(gè)區(qū)間劃分成一些單元區(qū)間，每個(gè)單元區(qū)間對(duì)應(yīng)線段樹中的一個(gè)葉結(jié)點(diǎn)。

線段樹的每個(gè)節(jié)點(diǎn)都表示一個(gè)區(qū)間，而根據(jù)線段樹的不同特征，線段樹的節(jié)點(diǎn)值可以表示這個(gè)區(qū)間里的最小值，最大值或者sum值等等。

最小線段樹

下面我們以最小線段樹為例來說明一下線段樹的特性：

如果原始數(shù)據(jù)是一個(gè)數(shù)組，我們也以數(shù)組來表示線段樹。

假設(shè)生成的線段樹的起點(diǎn)index=1，并且對(duì)線段樹中的每個(gè)非葉子節(jié)點(diǎn)index k來說，它的左子節(jié)點(diǎn)index=2* k, 而它的右子節(jié)點(diǎn)index=2* k+1 。

上圖中，標(biāo)黃色的是原始數(shù)組，總共有七個(gè)元素。

上面的樹形結(jié)構(gòu)就是根據(jù)原始

總結(jié)

以上是生活随笔為你收集整理的看动画学算法之:线段树-segmentTree的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。