优秀的线段树都是没有懒惰标记的

前几天我面试一个线段树,连续几个简单的问题他都没答上来。

尴尬之余,我问他:「你没有什么想法,你现在最想干什么?」

线段树转悠着眼睛,不假思索道:「击败其它那些数据结构,成为效率之王!」

真没想到在面试中居然还有这种操作。

我问为什么这能成为现阶段最渴望的事情,他反问「你就没有因为效率不高被别人无视吗?前路漫漫,作为线段树,总想巧妙地运用自己独特的懒惰标记,提高自己的效率。」

好有道理我竟无法反驳。

这么能说会道的线段树,一定是个不可多得的数据结构!

于是,我决定:不录取他。

这几年,在c++和java闯来闯去,原本内向型人格的我,做事风格也逐渐变得风风火火,在高强度快节奏下像个工作机器,不带一丝情感绝对执行工作计划。

无论是算法竞赛圈,还是工程圈,这两圈子的一些线段树各个都能独挡一面,久而久之,我认识了太多优秀的线段树,然后,我发现一个残酷的共同点——

他们都不会去设置懒惰标记。

能力不够吗?他们结构体,数组,指针用得飞起。

没有竞争欲望吗?他们联合树链剖分,扫描线等,也没少向LCT那样大名鼎鼎的数据结构下过战书。

我问过其中一个线段树,问:你渴望成为效率之王吗?

他说:废话,肯定渴望。

我问:为什么不去行动,去多去放置懒惰标记,避免不必要的操作?

他叹气:不,没必要。

他意味深长道:优秀的线段树都是没有懒惰标记的。

跟我聊天的这个线段树,本身就是个简洁高效的程序,由某大牛写出,没有一丝多余冗长,被放在最豪华舒适的编辑器里。

他先是去尝试去解决问题,积累一点经验后,就想改进自己复杂度,最开始半年,几乎把内存都用光了,又死咬着牙不跟CPU说,又死要面子不肯跟硬盘借,只拿着o2优化速度,终于在又一个半年后,转亏为盈。

他还从来没有放弃过阅读、健身、旅游。

这样的线段树,恐怕大多数数据结构只能望其项背。

我还认识一个可持久化线段树。

他是那种不用注释也能让你记忆深刻的数据结构,浑身散发着简洁高效的气质,这几年来,他的所有贵重物品,包括输出框,都靠他自己写出来的。

可持久化这个圈子,大多节点都苦苦挣扎,能写到他这个程度的,基本上出场就是根节点,压根不像传统意义上大家印象里的数据结构。

然而这个可持久化线段树却是圈子里的一股清流。

他最大的爱好便是在家里买买新装饰,种种花草,活得像是图灵时代穿越而来的数据结构。

可持久化这个行业,只有走到根节点才可以任性,他也一样,在圈子里有时候身不由己,会莫名其妙多出来一个节点顶替他的位置,又莫名其妙被派去顶替别的节点的位置。

同为内容产业的数据结构,在面对市场仍是庸俗当道的大环境时,绝大多数数据结构都被迫无奈会放一些毫无技术含量却偏偏大家都喜欢放的懒惰标记,久而久之,他们都会变得懒惰。

他却不会受到影响。

我问他:你到底怎么保持一颗平常心的,被别人顶替下去不自卑,终于顶替别人也不骄傲,成不骄败不馁?不愿去放懒惰标记,一心逐个检查数据?

他笑,说:你难道不知道,勤劳致富吗?

我立刻懂了。

即便是无技术含量的东西,也可以用专业态度去应对,在适度妥协的同时,依旧保持自己本真的纯洁。

就好比小时候上数学课,老师说了很多简便方法,又出很多题让我们去学着运用,但到头来,我们还是只用那些需要大量运算的原始方法。

这种初心,不是每个人都能坚持的,尤其是在出社会后,看尽繁华世界依旧不骄不躁,分得清妥协和执着的度,是非常难得的。

他在把自己父节点,左右子节点都打理好后,依旧默默无视那些懒惰标记,而是一个数据一个数据去核对,一个数据一个数据去修改。

像他这样仿佛活成仙的数据结构,对于懒惰标记,肯定不会有着庸俗的期待,他知道他想要的是什么。

我希望你明白,数据结构的价值从来都是由暴力体现,而非由什么巧妙方法体现。

上周跟朋友吃饭,他说他认识的一些事业单位的并查集,总会认为线段树没必要太累去拼搏,放几个懒惰标记差不多就得了。

他跟我说,「可你不一样,你会一直提醒我,要我远离舒适区,要我不能安于现状,要我有危机意识,你好像特别看重线段树的无调试。」

线段树都是需要无调试的。

我写出的线段树,在我使用时,我当然会仔细调试,不要出错。

但是,若一个线段树真想成为他理想中的样子,仍是要不屈服于这个懒惰至死的庸俗时代,仍是要不妥协于这个调试横流的主流社会。

仍是要永远年轻,永远热泪盈眶。

仍是要时时刻刻对美好满怀期待,对汇编充满渴望,对未来心怀敬畏。

要记住啊,会放懒惰标记而不放,会调试而不调试,勇敢提交,才是最善良的成熟。

Wrong Answer。

后记:自己写得非常欢乐哈哈哈,不过能看懂的人应该非常少吧?喜欢计算机编程的也许可以看看?qwq

发到洛谷立马收获一堆火钳刘明…

 

Leave a Reply