資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究使用Golang實現二叉索引樹（Fenwick樹）
二叉索引樹（也稱為Fenwick樹）是一種高效處理陣列上區間查詢和點更新的資料結構。在本文中，我們將探討兩種不同的方法來在Go語言中實現二叉索引樹，這裡的實現指的是我們執行二叉索引樹的主要操作：建立BIT（初始化）、更新和字首和查詢。
解釋
Fenwick樹是一種二叉樹結構，它可以高效地維護陣列的累積資訊，特別是字首和，並允許對範圍進行更快的更新和查詢。它應用於各種演算法和問題，例如查詢累積和和頻率計數。
Original Array: 1 2 3 4 5 6 7 8
Fenwick Tree: 1 3 3 10 5 11 7 36
| | | | |
1 2 4 8 16
Fenwick樹中的值透過以下方式獲得：
第一個索引包含原始陣列中單個元素1的累加和。
第二個索引包含索引1和2處元素的累加和，即1+2 =3。
第三個索引包含索引3處元素的累加和，即3。
第四個索引包含原始陣列中索引1、2、3和4處元素的累加和，即1+2+3+4 =10。
現在，第五個索引是原始陣列中單個元素5的累加和，即5。
第六個索引是索引5和6處元素的累加和，即11。
索引7包含索引7處單個元素的累加和，即7。
索引8包含原始陣列中所有元素的累加和，即1+2+3+4+5+6+7+8 = 36。
語法
func NewTrie() *Trie func NewBinaryIndexedTree(size int) *BinaryIndexedTree
此語法定義了一個名為NewBinaryIndexedTree的函式，它是BinaryIndexedTree（Fenwick樹）資料結構的建構函式，用於建立和初始化具有指定大小的新BinaryIndexedTree例項。
func (bit *BinaryIndexedTree) updateUtil(index, delta int)
此語法定義了一個名為updateUtil的函式，該函式更新Binary Indexed Tree（Fenwick樹）資料結構實現中特定索引處的累積和，表示為陣列。
演算法
首先用零初始化Fenwick樹，陣列大小增加一。
要進行更新，請遍歷Fenwick樹，將值新增到特定位置及其對應的祖先。
對於字首和，請遍歷Fenwick樹，從特定位置及其祖先減去值。
對於單個元素查詢，計算直到所需索引的字首和。
對於範圍查詢，計算給定範圍的字首和。
示例1
在這個例子中，我們使用包含樹的大小和陣列表示的BinaryIndexedTree結構體在Go語言中實現了一個二叉索引樹。NewBinaryIndexedTree函式初始化樹，同時適應基於1的索引。update方法沿著樹的路徑遞增樹節點，而tquery方法高效地計算字首和。
package main
import "fmt"
type BinaryIndexedTree struct {
n int
bit []int
}
func NewBinaryIndexedTree(size int) *BinaryIndexedTree {
return &BinaryIndexedTree{
n: size + 1,
bit: make([]int, size+1),
}
}
func (bit *BinaryIndexedTree) update(index, delta int) {
for i := index; i < bit.n; i += i & -i {
bit.bit[i] += delta
}
}
func (bit *BinaryIndexedTree) query(index int) int {
sum := 0
for i := index; i > 0; i -= i & -i {
sum += bit.bit[i]
}
return sum
}
func main() {
arr := []int{1, 2, 3, 4, 5}
size := len(arr)
bit := NewBinaryIndexedTree(size)
for i, val := range arr {
bit.update(i+1, val)
}
fmt.Println("Original Array:", arr)
fmt.Println("Prefix sum from index 1 to 4 (Method 1):", bit.query(4))
bit.update(3, 6)
fmt.Println("Updated Array:", bit.bit[1:])
fmt.Println("Prefix sum from index 1 to 4 (Method 1):", bit.query(4))
}
輸出
Original Array: [1 2 3 4 5] Prefix sum from index 1 to 4 (Method 1): 10 Updated Array: [1 3 9 16 5] Prefix sum from index 1 to 4 (Method 1): 16
示例2
在這個例子中，我們將使用包含樹的大小和陣列表示的BinaryIndexedTree結構體在Go語言中實現一個二叉索引樹。NewBinaryIndexedTree函式初始化樹，同時考慮基於1的索引。使用輔助遞迴函式進行樹更新和字首和計算，updateUtil函式修改樹路徑上的節點，而queryUtil函式計算字首和。
package main
import "fmt"
type BinaryIndexedTree struct {
n int
bit []int
}
func NewBinaryIndexedTree(size int) *BinaryIndexedTree {
return &BinaryIndexedTree{
n: size + 1,
bit: make([]int, size+1),
}
}
func (bit *BinaryIndexedTree) update(index, delta int) {
bit.updateUtil(index, delta)
}
func (bit *BinaryIndexedTree) updateUtil(index, delta int) {
if index <= 0 || index >= bit.n {
return
}
bit.bit[index] += delta
bit.updateUtil(index+(index&-index), delta)
}
func (bit *BinaryIndexedTree) query(index int) int {
return bit.queryUtil(index)
}
func (bit *BinaryIndexedTree) queryUtil(index int) int {
if index <= 0 {
return 0
}
return bit.bit[index] + bit.queryUtil(index-(index&-index))
}
func main() {
arr := []int{1, 2, 3, 4, 5}
size := len(arr)
bit := NewBinaryIndexedTree(size)
for i, val := range arr {
bit.update(i+1, val)
}
fmt.Println("Original Array:", arr)
fmt.Println("Prefix sum from index 1 to 4 (Method 2):", bit.query(4))
bit.update(3, 6)
fmt.Println("Updated Array:", bit.bit[1:])
fmt.Println("Prefix sum from index 1 to 4 (Method 2):", bit.query(4))
}
輸出
Original Array: [1 2 3 4 5] Prefix sum from index 1 to 4 (Method 2): 10 Updated Array: [1 3 9 16 5] Prefix sum from index 1 to 4 (Method 2): 16
現實生活中的應用
交通管理：在交通管理系統中使用Fenwick樹可以對與特定區域內車輛移動相關的資料進行結構化和檢索，從而有助於最佳化交通監控和分析操作。
感測器資料分析：在物聯網(IoT)應用中使用Fenwick樹可以更有效地儲存和分析感測器資料。這包括計算關鍵指標，例如指定時間段內的平均溫度和溼度測量值。
結論
Fenwick樹是一種二叉樹結構，它可以高效地維護陣列的累積資訊。在本文中，我們研究了在Go語言中實現二叉索引樹的兩個不同示例，為陣列上的累積頻率查詢提供了高效的操作。第一個示例使用陣列來簡化實現和提高記憶體效率，使其成為實際應用的首選。另一方面，方法2提供了對二叉索引樹樹狀結構的遞迴洞察，證明其對教育目的很有價值。
136 次瀏覽
