在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
}
