比较简单的一次周赛,最后的压轴题是一道很典型的线段树或者树状数组题目。正好可以借这道题目分析一下线段树和树状数组的区别。
1648. 销售价值减少的颜色球M 思路更重要
比较朴素的思路是维护一个优先队列的思路,每次取出最多的那个数字出售,但是这样的复杂度太高了。观察可以发现,如果最多的是5,次多的是2,我们可以把最多的数字卖到只剩两个。并且在出售的过程中其实是一个等差数列的求和问题。
1 | class Solution { |
1649. 通过指令创建有序数组H 线段树,树状数组
一道很经典的板子题目,比较简单可以用数据结构解决的思路就是采用线段树和树状数组。正好我们可以借助这个题目对比一下思路有共同点的两个数据结构。树状数组能有的操作,线段树一定有;
线段树有的操作,树状数组不一定有
- 线段树:可以在$O(lgn)$的复杂度内维护区间整体的抬升,也就是对[3,8]区间整体加2这种操作,同样是可以维护一下区间和等信息。
- 树状数组:可以在$O(lgn)$的复杂度内维护单点的修改,主要是维护了区间信息,修改是针对单点的。但是整体的复杂度是比线段树低的。
首先给出树状数组的代码,在写代码时候,已经尽量做到了模块化。
1 | class Solution { |
然后再贴上线段树的方法,有点杀鸡用牛刀了。
1 | class Solution { |