資料結構中的區間樹

在本節中，我們將瞭解什麼是區間樹。在討論之前，讓我們看一個問題。

假設我們有一個數組 arr[0,…,n-1]，我們可以執行以下操作 −

  • 查詢從索引 l 到 r 的元素的和，其中 0 ≤ l ≤ r ≤ n-1

  • 將陣列中指定元素的值更改為新值 x。我們需要執行 arr[i] = x。i 的範圍為 0 到 n – 1。

我們可以使用區間樹來解決此問題。區間樹可以幫助我們在 O(log n) 時間內獲取和並進行查詢。因此，讓我們看看如何表示這一點 −

  • 葉節點是給定陣列的元素

  • 每個內部節點都表示葉節點的某些合併。合併可能在不同情況下有所不同。此處合併是節點下葉的和。

假設我們有一個類似 [1, 3, 5, 7, 9, 11] 的陣列。因此，區間樹將是

更新於：2020-08-11

405 次瀏覽

開啟您的 職業

完成教程獲得認證

開始
廣告