亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

psychola / 2379人閱讀

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

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

簡介

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

可實現(xiàn)的功能

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

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

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

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

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

代碼實現(xiàn)

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

初始化

這里創(chuàng)建一個數(shù)組dat[]并賦予初始最大值, 為了讓其成為一棵完美的二叉樹, 便于計算, 我們把n擴大到2的冪, 由于我們在數(shù)組中填充了int32的最大整數(shù)2147483647, 所以多余出來的的元素總是最大值, 不會影響原來區(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ù)組, 下標(biāo)為i的子節(jié)點為i*2+1 和 i*2+2, a0為根節(jié)點, 每次更新時, 首先更新葉子節(jié)點, 之后一層層往上更新, 節(jié)點a[k] = min(a[k * 2 + 1],a[k * 2 + 2]), 操作在O(log n)的時間內(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])
查詢元素

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

k 當(dāng)前計算的節(jié)點

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

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

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é)尾

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

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

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

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/42656.html

相關(guān)文章

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

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

    genedna 評論0 收藏0

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

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

    waltr 評論0 收藏0

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

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

    shaonbean 評論0 收藏0

  • LuxTdmZtIC

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

    CoffeX 評論0 收藏0

  • LuxTdmZtIC

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

    tuantuan 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<