杭州建网站,荣昌集团网站建设,网站下载系统,大连软件开发网站建设树状数组#xff08;Binary Indexed Tree, BIT#xff09;#xff0c;又称为斐波那契堆#xff0c;是一种数据结构#xff0c;用于高效地解决以下问题#xff1a;
单点更新#xff1a;在数组的某个位置增加或减少一个值。区间查询#xff1a;查询数组中一段连续区间的…树状数组Binary Indexed Tree, BIT又称为斐波那契堆是一种数据结构用于高效地解决以下问题
单点更新在数组的某个位置增加或减少一个值。区间查询查询数组中一段连续区间的元素之和。
树状数组的核心思想是使用一个数组来存储原数组的累积和然后利用数组的偏移来快速计算区间和。这种数据结构在时间复杂度上具有优势对于单点更新和区间查询它们的时间复杂度都是 (O(\log n))。
以下是 Python 中实现树状数组的基本操作的示例代码
class BinaryIndexedTree:def __init__(self, size):self.size sizeself.tree [0] * (size 1)def _parent(self, index):while index 1:index - index -indexreturn indexdef update(self, index, delta):while index self.size:self.tree[index] deltaindex self._parent(index)def query(self, index):result 0while index 0:result self.tree[index]index - self._parent(index)return result# 使用示例
bit BinaryIndexedTree(10)
bit.update(1, 5) # 将索引1的值增加5
bit.update(3, 7) # 将索引3的值增加7print(bit.query(4)) # 查询索引1到4的和应为12在这个例子中BinaryIndexedTree 类有三个方法
__init__初始化树状数组。update在数组的指定索引位置增加一个值。query查询从1到指定索引位置的累积和。
请注意树状数组通常从索引1开始而不是0这与 Python 中列表的索引方式不同。如果你需要从0开始可以在调用 update 和 query 方法时将索引减1。
