数据结构暂时告一段落,其实也就是理解了理解思想,看了几个比较典型的模板题目。

最开始的时候就是树状数组,树状数组就是一种区间查询,维护前缀和,前缀和经常的用处就是计算任意区间的差值,前缀和效率比较高。

再就是RMQ问题,RMQ问题有多种解法,首先线段树是一定可以解决的,线段树的功能是非常强大的,还有另一种动态规划解法,ST算法。在数据结构中,最好吃那个用的就是二进制,在二进制的使用下,能把算法复杂度降低到O(logN),查询是O(1)的复杂度,关键是慢慢的也习惯了二进制的算法。

还有一个是线段树,线段树的思想就是二分每个节点以结构体的方式存储,结构体包含以下几个信息:区间左端点、右端点;这个区间要维护的信息(事实际情况而定,数目不等)。具体的在详细说。

还有就是树剖,树剖主要是对一条链进行修改,思想没看懂,例题也没看太多。

平衡树,平衡树基本的二叉搜索树,二叉搜索树也是个很好的结构。查找速度也是非常的快,所以具体情况具体分析。选择合适的结构。还有多去看书,多去做题。这个尽量自己找时间吧,还是学习为主,而且都快要考试了!

发表评论

电子邮件地址不会被公开。 必填项已用*标注