刷题前唠嗑

LeetCode? 启动！！！

今天是中等题，貌似挺简单的，先试试水

题目：区域和检索 - 数组可修改

题目链接：307. 区域和检索 - 数组可修改

题目描述

代码与解题思路

type NumArray struct {arr []int
}func Constructor(nums []int) NumArray {return NumArray { arr: nums }
}func (this *NumArray) Update(index int, val int)  {this.arr[index] = val
}func (this *NumArray) SumRange(left int, right int) (ans int) {for _, v := range this.arr[left:right+1] {ans += v}return ans
}/*** Your NumArray object will be instantiated and called as such:* obj := Constructor(nums);* obj.Update(index,val);* param_2 := obj.SumRange(left,right);*/

难道真这么简单？

超时了。。。

难道需要用前缀和？失败。。

偷看大佬题解

啊？这是中等题？我真是晕倒了，树状数组。。。

但没办法，我就马上现学了一下树状数组是什么，树状数组的模板是什么样的，然后对照着别人的题解套用了一下，新知识+1：树状数组，具体的证明没看懂，但是模板学个差不多就行了，下次再遇到就下次再说

至于前几天的线段树和并查集，我到时候也抽时间学一下，争取下一次遇到至少要能看的懂题解才行，可不能遇到一次就 CV 一次。。。

type NumArray struct {nums []inttree []int
}func Constructor(nums []int) NumArray {this := NumArray{make([]int, len(nums)), make([]int, len(nums)+1)}for i, v := range nums {this.Update(i, v)}return this
}func (this *NumArray) Update(index int, val int)  {delta := val-this.nums[index]this.nums[index] = valfor i := index+1; i < len(this.tree); i += i & -i {this.tree[i] += delta}
}func (this *NumArray) prefixSum(i int) (s int) {for ; i > 0; i -= i & -i {s += this.tree[i]}return s
}func (this *NumArray) SumRange(left int, right int) int {return this.prefixSum(right+1)-this.prefixSum(left)
}/*** Your NumArray object will be instantiated and called as such:* obj := Constructor(nums);* obj.Update(index,val);* param_2 := obj.SumRange(left,right);*/

树状数组还是很巧妙的，通过 logn 的复杂度查找到数组区间的和

结语

今日收获：初识树状数组

以后看到需要频繁查找数组区间和的题目就知道得用树状数组了。。