【刷题日记】307. 区域和检索 - 数组可修改

本次刷题日记的第 24 篇，力扣题为：307. 区域和检索 - 数组可修改 ，中等

一、题目描述：

清明小长假第 2 天，咱们再来继续刷 leetcode 每日一题

看到这道题啥感受，我的第一感受就是可能我出去玩的时间要被缩减了，诶，就是菜

这道题可能和其他的题还不太一样，这算是写一个微小的功能，而不是仅仅写一个函数，不过没事，我们仍然可以解决他，来我们一起来分析一波

二、这道题考察了什么思想？你的思路是什么？

咱们仔细看这道题，给出了我们哪些重点信息呢：

• 题目给出的已知条件，具体的操作数和具体的数组，对我们有 2 个要求，第 1 就是通过 update 来将指定索引位置上的值修改成期望的值，第 2 就是给出左右区间，我们可以迅速的查询出他们的区间和
• 看了这个题，我们需要完成这么几件事情：

• 完成对 NumArray 的定义
• 构造函数的处理
• Update 函数的实现
• SumRange 函数的实现

对于没有这类题刷题经验的我们来说，稍微思考一下，倒是可以写出能够计算出期望结果的代码，那就是常规做法，遍历数组，累加

类似于这样的做法：

你要说这种代码有啥问题吗？

你说有问题吧，其实他也解决了部分问题，你说没有问题吧，其实他对于用例数据量很大的时候，会超时，是没有办法 AC 的

那么我们就要考虑别的方式了，思考了一下，暂时先用一个简单的方法来计算区间和吧

咱们可以使用分段分组的方式来处理

此处我们使用一个示例来推演一下如何计算区间和的，对于 update 函数的话，这个就不做过多解释了

例如我们可以自定义一个示例，对应的数组是 [1, 3, 4, 5, 7, 8, 9]，那么咱们来看图

根据上述的示例推演的话，xdm 也可以自己自定义一个例子来推演一下，就能很快的理解了

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，此处需要注意 SumRange 的情况分类

编码如下：

type NumArray struct {
    nums ,sums[]int
    size int
}
func Constructor(nums []int) NumArray {
    length := len(nums)
    size :=int(math.Sqrt(float64(length))) 
    // 定义个记录每一块区间和的切片，大小为
    sums := make([]int,(length / size)+1)
    for i,n := range nums{
        // 对于每一个区间求和
        sums[i/size] += n
    }
    return NumArray{nums,sums,size}
}
func (this *NumArray) Update(index int, val int)  {
    // 处理该值所在区间的数字
    this.sums[index/this.size] += val - this.nums[index]
    this.nums[index] = val
}
func (this *NumArray) SumRange(left int, right int) (ans int) {
    a := left/this.size
    b := right/this.size
    // 说明 left 和 right 对应的区间是同一块
    if a == b{
        for i:=left;i<=right;i++ {
         ans += this.nums[i]
        }
        return
    }
    // left 和 right 不是同一块，至少是 2 块以上的情况
    // 处理  left 到 所在块的内容
    for i := left ; i<(a+1)*this.size;i++{
         ans += this.nums[i]
    }
    // 处理left 下一块到 right 所在块的内容，此处正好可以使用 sum 数组中的内容
    for i :=a+1;i<b;i++{
         ans += this.sums[i]
    }
    // 处理 right 所在块的起点，到 right 的内容
    for i:=b*this.size;i<= right ;i++ {
        ans += this.nums[i]
    }
    return
}

四、总结：

本次题目的时间复杂度是就需要按照函数来区分了

• Constructor 时间复杂度是 O(n) ,
• update 时间复杂度是 O(1)
• SumRange 时间复杂度是 O(根号 n)

空间复杂度的话，咱们是引入了一个 sums 数组和 ，咱们 sums 的数组长度，取决于咱们切割数组的份数，因此是 O(根号n)

原题地址：307. 区域和检索 - 数组可修改

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~