树状数组-leetcode-307

在leetcode-307题目中初次接触了树状数组这个数据结构。树状数组用于高效地对数组进行更新以及求前缀和。

lowBit(x) 表示数组x的最后一位1所表示的数字

构造树状数组需要遍历一次数组。遍历到元素x的时候，使用x += lowBit(x)寻找被影响的数组下标
查询树状数组时使用x -= lowBit(x)寻找小于x的下一区间

LeetCode 307 题目的完整代码如下

type NumArray struct {
    sums []int
    nums []int
}

func lowBit(x int) int {
    return x & (-x)
}

func Constructor(nums []int) NumArray {
    n := NumArray{
        nums: nums,
        sums: make([]int, len(nums)+1),
    }
    for i := 0; i < len(nums); i++ {
        x := i + 1
        for x < len(n.sums) {
            n.sums[x] += nums[i]
            x += lowBit(x)
        }
    }
    return n
}

func (this *NumArray) Update(index int, val int) {
    x := index + 1
    for x < len(this.sums) {
        this.sums[x] = this.sums[x] - this.nums[index] + val
        x += lowBit(x)
    }
    this.nums[index] = val
}

func (this *NumArray) SumRange(left int, right int) int {
    return this.query(right+1) - this.query(left)
}

func (this *NumArray) query(x int) int {
    s := 0
    for x != 0 {
        s += this.sums[x]
        x -= lowBit(x)
    }
    return s
}

参考资料

1. https://blog.csdn.net/Yaokai_AssultMaster/article/details/79492190
2. https://leetcode-cn.com/problems/range-sum-query-mutable/solution/-by-hu-ge-8-t4rn/