Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

go实现树状数组

  1. User

    go实现树状数组

  2. 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的位置的值即可。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.