一种节省空间的基于递归的线段树实现

使用先序遍历的节点访问顺序重新给左右儿子编号,大大节省了空间

自古以来,实现线段树所需要的数组空间大小有着比较激烈的争论。一种基于递归的线段树实现认为至少需要 $\mathcal {O}(4n)$ 的空间,而另一种基于直接循环的方法认为其实只需要 $2n-1$ 的空间。关于为什么基于递归的方法需要 $\mathcal {O}(4n)$ 的严格证明可以去网上搜索,或者 这里 提供了一个简易的证明方法。总的来说,基于递归的线段树实现起来更加直观,但由于 dummy node 的存在造成了空间的浪费。而基于直接循环的方法对实现的要求更高。本文介绍了一个基于递归的线段树实现,通过改变每个节点的左右儿子的编号高效的利用了空间,使得基于递归的线段树也只需要 $2n-1$ 的空间。另外,关于基于循环的线段树实现方法,可以参考 这篇博客

阅读更多

[算法笔记 3] Codeforces - 1139 D. Steps to One

如何求出 1-n 每个数的全部因子?
在继续往下阅读之前,请先想一想,如果给定一个 $n,n\leq100000$,让你求出 1~n 的全部因子,你需要如何实现?要编写多少行代码?复杂度如何?

可能会这么考虑,如果对于每个数 $x$,枚举 1~n 逐一判断每个数是否是 $x$ 的因子,复杂度为 $\mathcal {O}(n^2)$,显然是不可接受的,即使枚举到 $\sqrt n$,复杂度也有 $\mathcal {O}(n \sqrt n)$,依然太大,有没有更好的办法?

阅读更多

[算法笔记 2] 动态规划

关于动态规划的一些新感悟。
自从这学期学校开设了算法课之后,受到算法课老师的鼓励我突然又有了写算法题的动力。特别是老师第一节课重新回顾的动态规划算法,使我对动态规划有了一些新的理解。

其实之前我一直对动态规划有一种说不出来的敬而远之地感受。我最早接触动态规划算法可以追溯到高中的时候了,那个时候去少年宫学各种算法 (顺便和小伙伴们愉快的玩耍),记得学到最短路径的 dijkstra 算法,当时学了之后不由感叹,哇!还能想出这样的算法,也太强了吧!这怎么想得出来嘛!所以从那个时候起我每次知道某道题要用动态规划去求解时总会不由自主地头大。因此其实很长一段时间以来,我的动态规划的水平仅仅停留在最粗浅的三角形路径最大问题上 (就是那个很 naive 的给一个三角形让你求一条路径使得从左上角到右上角权值和最大)。

阅读更多

最近完成的一些算法题

一个多月没写博客了,赶紧填个坑。

kickstart
离上一篇博客居然已经过去一个多月啦,看来研究生还是要比本科忙多了,每天都有事情要做。最近呢,就是参加了昨天的 Google Kickstart Round G 2018,本来顺利做完了 2.5 题,做完的时候有 60 名左右,结果有个大数据犯了一个低级错误,结果一个大数据挂了,最后只有 100 多名!啊!好气啊!看了一下题解,发现方法和我自己实现的方法差挺多的,所以想简单讲一下我的算法。

阅读更多