国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

快速區間查詢算法 - 線段樹

psychola / 2317人閱讀

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

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

簡介

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

可實現的功能

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

求區間最小值(最小值)

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

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

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

求區間的和

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

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

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

代碼實現

這里我們以求區間最小值內的最小值為例, 用Python來實現原始的一棵線段樹

初始化

這里創建一個數組dat[]并賦予初始最大值, 為了讓其成為一棵完美的二叉樹, 便于計算, 我們把n擴大到2的冪, 由于我們在數組中填充了int32的最大整數2147483647, 所以多余出來的的元素總是最大值, 不會影響原來區間的結果

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)]
更新元素

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

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)區間內的最小值, 參數k, l, r是輔助參數

k 當前計算的節點

l, r 當前節點區間的范圍

當[a,b), 不在k節點管理的區間[l, r)內時, 直接返回INT_MAX
當[a,b), 重合于k節點管理的區間[l, r)時, 直接返回k節點的值
否則, 遞歸k的兩個子節點, 返回其中的最小值

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

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

歡迎關注我的博客公眾號

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/42656.html

相關文章

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

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

    genedna 評論0 收藏0

  • 我理解的數據結構（八）—— 線段樹（SegmentTree）

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

    waltr 評論0 收藏0

  • 我理解的數據結構（八）—— 線段樹（SegmentTree）

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

    shaonbean 評論0 收藏0

  • LuxTdmZtIC

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

    CoffeX 評論0 收藏0

  • LuxTdmZtIC

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

    tuantuan 評論0 收藏0

發表評論

0條評論

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