成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

快速區(qū)間查詢算法 - 線段樹(shù)

psychola / 2328人閱讀

摘要：原博地址簡(jiǎn)介線段樹(shù)算法是一種快速查詢一段區(qū)間內(nèi)的信息的算法由于其實(shí)現(xiàn)簡(jiǎn)單所以廣泛應(yīng)用于程序設(shè)計(jì)競(jìng)賽中。線段樹(shù)是一棵完美二叉樹(shù)即所有的葉子節(jié)點(diǎn)的深度均相同并且所有的非葉子節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。

原博地址https://laboo.top/2018/11/24/xds/#more

簡(jiǎn)介

線段樹(shù)算法是一種快速查詢一段區(qū)間內(nèi)的信息的算法, 由于其實(shí)現(xiàn)簡(jiǎn)單, 所以廣泛應(yīng)用于程序設(shè)計(jì)競(jìng)賽中。
線段樹(shù)是一棵完美二叉樹(shù), 即所有的葉子節(jié)點(diǎn)的深度均相同, 并且所有的非葉子節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)區(qū)間, 這個(gè)區(qū)間為父節(jié)點(diǎn)二分后的子區(qū)間, 根節(jié)點(diǎn)維護(hù)整個(gè)區(qū)間, 葉子節(jié)點(diǎn)維護(hù)單個(gè)元素, 當(dāng)元素個(gè)數(shù)為n時(shí), 對(duì)區(qū)間的操作都可以在O(log n)的時(shí)間內(nèi)完成, 因?yàn)榇藭r(shí)樹(shù)的深度為log2 n + 1, 每次操作只需從葉子節(jié)點(diǎn)開(kāi)始, 往上更新至根節(jié)點(diǎn), 每層只需更新相關(guān)的一個(gè)區(qū)間即可, 操作次數(shù)log2 n + 1, 即在O(log n)的時(shí)間內(nèi)可完成。

可實(shí)現(xiàn)的功能

線段樹(shù)可以提供不同的功能, 例如最常見(jiàn)的求區(qū)間內(nèi)的最大最小值和求區(qū)間內(nèi)的和, 還有其他類(lèi)似的功能, 實(shí)現(xiàn)思路基本相同

求區(qū)間最小值(最小值)

給定任意數(shù)列[a0, a1,...,an-1], 在O(log n)的時(shí)間內(nèi)完成下列的兩種操作

query(s, t) 求 [as,as+1,...,at-1] 內(nèi)的最小值(最小值)

update(i, x) 把 ai 的值改為 x

求區(qū)間的和

給定初始值全為0的數(shù)列[a0, a1,...,an-1], 在O(log n)的時(shí)間內(nèi)完成下列的兩種操作

query(s, t) 求 [as,as+1,...,at-1] 內(nèi)的和

add(i, x) 執(zhí)行 ai += x

代碼實(shí)現(xiàn)

這里我們以求區(qū)間最小值內(nèi)的最小值為例, 用Python來(lái)實(shí)現(xiàn)原始的一棵線段樹(shù)

初始化

這里創(chuàng)建一個(gè)數(shù)組dat[]并賦予初始最大值, 為了讓其成為一棵完美的二叉樹(shù), 便于計(jì)算, 我們把n擴(kuò)大到2的冪, 由于我們?cè)跀?shù)組中填充了int32的最大整數(shù)2147483647, 所以多余出來(lái)的的元素總是最大值, 不會(huì)影響原來(lái)區(qū)間的結(jié)果

def init(self, n):
    self.INT_MAX = 2147483647
    self.n = 1
        
    while self.n < n:
        self.n *= 2

    self.dat = [self.INT_MAX for i in range(2 * self.n - 1)]
更新元素

我們把一棵完美二叉樹(shù)壓成一個(gè)數(shù)組, 下標(biāo)為i的子節(jié)點(diǎn)為i*2+1 和 i*2+2, a0為根節(jié)點(diǎn), 每次更新時(shí), 首先更新葉子節(jié)點(diǎn), 之后一層層往上更新, 節(jié)點(diǎn)a[k] = min(a[k * 2 + 1],a[k * 2 + 2]), 操作在O(log n)的時(shí)間內(nèi)完成

def update(self, k, a):
    k += self.n - 1
    self.dat[k] = a
    while k > 0:
        k = (k - 1) // 2
        self.dat[k] = min(self.dat[k * 2 + 1],self.dat[k * 2 + 2])
查詢?cè)?/b>

query的功能為查詢[a, b)區(qū)間內(nèi)的最小值, 參數(shù)k, l, r是輔助參數(shù)

k 當(dāng)前計(jì)算的節(jié)點(diǎn)

l, r 當(dāng)前節(jié)點(diǎn)區(qū)間的范圍

當(dāng)[a,b), 不在k節(jié)點(diǎn)管理的區(qū)間[l, r)內(nèi)時(shí), 直接返回INT_MAX
當(dāng)[a,b), 重合于k節(jié)點(diǎn)管理的區(qū)間[l, r)時(shí), 直接返回k節(jié)點(diǎn)的值
否則, 遞歸k的兩個(gè)子節(jié)點(diǎn), 返回其中的最小值

def query(self, a, b, k, l, r):
    if r <= a or b <= l:
        return self.INT_MAX

    if a <= l and r <= b:
        return self.dat[k]
    else:
        vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)
結(jié)尾

至此我們就簡(jiǎn)單地實(shí)現(xiàn)了一棵線段樹(shù), 這只是線段樹(shù)的其中一種形式, 線段樹(shù)還有其他的變體。線段樹(shù)的使用實(shí)例可以看我的另一篇文章https://laboo.top/2018/11/02/acm-lc-45/#more

歡迎關(guān)注我的博客公眾號(hào)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/42656.html

相關(guān)文章

  • 面試算法實(shí)踐與國(guó)外大廠習(xí)題指南

    摘要：面試算法實(shí)踐與國(guó)外大廠習(xí)題指南翻譯自維護(hù)的倉(cāng)庫(kù)，包含了在線練習(xí)算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。面試算法實(shí)踐與國(guó)外大廠習(xí)題指南在線練習(xí)在線面試編程數(shù)據(jù)結(jié)構(gòu)鏈表即是由節(jié)點(diǎn)組成的線性集合，每個(gè)節(jié)點(diǎn)可以利用指針指向其他節(jié)點(diǎn)。 面試算法實(shí)踐與國(guó)外大廠習(xí)題指南 翻譯自 Kevin Naughton Jr. 維護(hù)的倉(cāng)庫(kù) interviews，包含了在線練習(xí)、算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。筆者發(fā)現(xiàn)正好和...

    genedna 評(píng)論0 收藏0

  • 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線段樹(shù)（SegmentTree）

    摘要：示例解題代碼注意，如果要在上提交解答，必須把接口和類(lèi)的代碼一并提交，這里并沒(méi)有在寫(xiě)類(lèi)中 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線段樹(shù)（SegmentTree） 一、什么是線段樹(shù) 1.最經(jīng)典的線段樹(shù)問(wèn)題：區(qū)間染色有一面墻，長(zhǎng)度為n，每次選擇一段墻進(jìn)行染色，m次操作后，我們可以看見(jiàn)多少種顏色？m次操作后，我們可以在[i, j]區(qū)間內(nèi)看見(jiàn)多少種顏色？showImg(https://segmentfau...

    waltr 評(píng)論0 收藏0

  • 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線段樹(shù)（SegmentTree）

    摘要：示例解題代碼注意，如果要在上提交解答，必須把接口和類(lèi)的代碼一并提交，這里并沒(méi)有在寫(xiě)類(lèi)中 我理解的數(shù)據(jù)結(jié)構(gòu)（八）—— 線段樹(shù)（SegmentTree） 一、什么是線段樹(shù) 1.最經(jīng)典的線段樹(shù)問(wèn)題：區(qū)間染色有一面墻，長(zhǎng)度為n，每次選擇一段墻進(jìn)行染色，m次操作后，我們可以看見(jiàn)多少種顏色？m次操作后，我們可以在[i, j]區(qū)間內(nèi)看見(jiàn)多少種顏色？showImg(https://segmentfau...

    shaonbean 評(píng)論0 收藏0

  • LuxTdmZtIC

    摘要：轉(zhuǎn)載史上最簡(jiǎn)單的平衡樹(shù)無(wú)旋作者博客地址使用此文件時(shí)請(qǐng)保留上述信息謝謝合作覺(jué)得文章不錯(cuò)請(qǐng)點(diǎn)擊鏈接為博客點(diǎn)贊高能預(yù)警所有示例代碼都是數(shù)組版的歡迎前置知識(shí)線段樹(shù)請(qǐng)確保你完全理解最基礎(chǔ)的線段樹(shù)和區(qū)間加法和區(qū)間求和一簡(jiǎn)介無(wú)旋又稱(chēng)是范浩強(qiáng)大佬發(fā)明的一種 【轉(zhuǎn)載】史上最簡(jiǎn)單的平衡樹(shù)——無(wú)旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    CoffeX 評(píng)論0 收藏0

  • LuxTdmZtIC

    摘要：轉(zhuǎn)載史上最簡(jiǎn)單的平衡樹(shù)無(wú)旋作者博客地址使用此文件時(shí)請(qǐng)保留上述信息謝謝合作覺(jué)得文章不錯(cuò)請(qǐng)點(diǎn)擊鏈接為博客點(diǎn)贊高能預(yù)警所有示例代碼都是數(shù)組版的歡迎前置知識(shí)線段樹(shù)請(qǐng)確保你完全理解最基礎(chǔ)的線段樹(shù)和區(qū)間加法和區(qū)間求和一簡(jiǎn)介無(wú)旋又稱(chēng)是范浩強(qiáng)大佬發(fā)明的一種 【轉(zhuǎn)載】史上最簡(jiǎn)單的平衡樹(shù)——無(wú)旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

    tuantuan 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<