gpt-3.5-turbo-0301· OpenAI
WildChat-4.8M (AI2)
go实现树状数组
- User
go实现树状数组
- Assistant
树状数组(Fenwick Tree)是一种利用树状结构实现的数据结构,主要用于维护前缀和。其本质是一个数组通过预处理得到了一些前缀和,用于快速求解区间和。下面是一段go实现的树状数组代码:
type FenwickTree struct { tree []int size int } func NewFenwickTree(n int) *FenwickTree { return &FenwickTree{make([]int, n+1), n} } func (t *FenwickTree) lowBit(x int) int { return x & (-x) } func (t *FenwickTree) update(index int, val int) { for index <= t.size { t.tree[index] += val index += t.lowBit(index) } } func (t *FenwickTree) query(index int) int { sum := 0 for index > 0 { sum += t.tree[index] index -= t.lowBit(index) } return sum }其中,
NewFenwickTree函数用于创建一颗新的树状数组,update函数用于更新指定位置的值,query函数用于查询指定区间的前缀和。具体实现时借助了树状数组的性质,使用lowbit函数计算节点之间的距离。在更新或查询时,依次修改或查询距离指定位置不超过lowbit的位置的值即可。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.