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 Tree)数据结构的构造函数，用于创建和初始化具有指定大小的新 BinaryIndexedTree 实例。
func (bit *BinaryIndexedTree) updateUtil(index, delta int)
该语法定义了一个名为 updateUtil 的函数，该函数更新二叉索引树 (Fenwick Tree) 数据结构实现中特定索引处的累积和，以数组表示。
算法
首先用零初始化 Fenwick Tree，数组大小增加一。
要更新，请遍历 Fenwick Tree，将值添加到特定位置及其相应的祖先。
对于前缀和，遍历 Fenwick Tree，从特定位置及其祖先中减去值。
对于单个元素查询，计算到所需索引的前缀和。
对于范围查询，计算给定范围的前缀和。
示例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("原始数组:", arr)
fmt.Println("从索引 1 到 4 的前缀和(方法 1):", bit.query(4))
bit.update(3, 6)
fmt.Println("更新后的数组:", bit.bit[1:])
fmt.Println("从索引 1 到 4 的前缀和(方法 1):", bit.query(4))
}
输出
原始数组:[1 2 3 4 5] 从索引 1 到 4 的前缀和(方法 1):10 更新后的数组:[1 3 9 16 5] 从索引 1 到 4 的前缀和(方法 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("原始数组:", arr)
fmt.Println("从索引 1 到 4 的前缀和(方法 2):", bit.query(4))
bit.update(3, 6)
fmt.Println("更新后的数组:", bit.bit[1:])
fmt.Println("从索引 1 到 4 的前缀和(方法 2):", bit.query(4))
}
输出
原始数组:[1 2 3 4 5] 索引 1 到 4 的前缀总和(方法 2):10 更新后的数组:[1 3 9 16 5] 索引 1 到 4 的前缀总和(方法 2):16
实际实施
交通管理:在交通管理系统中使用 Fenwick 树可以构建和检索与定义区域内车辆移动相关的数据，从而有助于优化交通监控和分析操作。
传感器数据分析:物联网 (IoT) 应用中的 Fenwick 树可以实现更有效的传感器数据存储和分析。这涉及计算关键指标，例如指定时间段内的平均温度和湿度测量值。
结论
Fenwick Tree 是一种二叉树结构，可有效维护有关数组的累积信息。在本文中，我们研究了两个不同的示例，以在 Go 中实现二叉索引树，为数组上的累积频率查询提供有效的操作。第一个示例使用数组来简化实现和提高内存效率，使其成为实际使用的首选。另一方面，方法 2 提供了对二叉索引树的树状结构的递归洞察，证明对教育目的很有价值。
