数据结构
网络
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 次浏览
