ZKW线段树,放弃谷歌百万年薪的男人

作者: | 更新日期:

上周计划写 ZKW 线段树(ZWK线段树),这周背后的男人火了。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

一、背景

大概上周六的时候,一个小朋友问题一道线段树的题。
问自己的算法为啥超时了。

我当初略读了了下题,发现是标准的线段树题。
就猜测可能是区间更新的时候,没有延迟标记导致超时的。

但是一细看题,是单点更新,那就是最裸的线段树模板理论上也应该通过的。

理论与实际不一样的时候,只好 show code 来看具体的原因了。
当然,show code 之前,我先套用自己的线段树模板提交了一发,一下就通过了。

PS:后台回复关键字“线段树”获取模板代码。

既然理论没问题,那肯定是代码写的有问题了。

打开代码一看,原来是 ZKW 线段树被写错了。

ZKW 线段树,永远的神。

二、ZKW 线段树

线段树主要用于解决一些区间修改、区间查询的问题。
修改可能是区间都设置为某个值,也可能是区间都加上某个值。
查询可能是区间和,也可能是区间最值,或者某种规则下的最优值。

朴素的线段是从上到下计算区间的。
这就导致叶子节点在哪一层完全未知,即部分叶子在倒数第一层,部分叶子在倒数第二层。
想要得到得到叶子的位置,必须从上到下递归计算出来。

而 ZKW 线段树则是从下到上计算的,类似于堆或者哈夫曼树。
叶子节点在最底层,从下到上两两合并,就构造出一个完全二叉树。
当然,最右侧可能都空的,但是左侧一定是满的。

由于 ZKW 类似于完全二叉树,非叶子节点个数就固定了。
这样,通过找到最底层第一个叶子节点的位置,其他叶子节点的下标都可以 O(1) 确定。

ZKW 线段与传统线段树相比,优点是实现简单,缺点是较难理解。

三、ZKW 背后的男人

清华大学张昆玮在 2010 年的《统计的力量——线段树详细教程》中,介绍了ZKW 线段树,从此流传甚广。

在大学生程序编程竞赛圈子里,合格的竞赛者,没人不知道 ZKW 线段树吧。

PS:《统计的力量》这个资料我上传到微云网盘。
想学习 ZKW 线段树的同学,后台回复“ZKW” 或者“统计的力量” 获取相关资料。

而这几天在豆瓣上,ZKW 张昆玮第三次火了(第一次离开谷歌回到小县城、第二次发相亲贴)。

原因是清华姚班的张昆玮在豆瓣上发了一个相亲贴,结果被国内的拳师毫无道理的打拳。

张昆玮是一个谦虚的人,豆瓣上没有把自己曾经的光环写到自己的相亲贴上。

拳师只看到了一点点信息“山西家乡小城、月入五万、二本教书、小胖子自拍照”,就开始疯狂嘲讽张昆玮。

而背后的张昆玮到底有多牛?

下面罗列一下。

1、NOI 比赛两次获得金牌,保送清华(少年天才)。
2、ACM 全球亚军(全球顶级人才)。
3、2009级清华姚班毕业生(在顶级学府顶级教授名下)。
4、毕业后曾就职于摩根大通、谷歌公司(年薪几百万)。
5、放弃一切当月薪几千的计算机老师(谁能做得到?)

如果只看前 4 点,我们可以称之为世界顶级人才,仅仅代表技术厉害。
看到第 5 点,说明张昆玮的思想也非常值得人敬佩,是一个独立思考和自由精神的人。

四、最后

张昆玮离开谷歌的时候,曾说过一句话:我不愿意像成功学说的一样,为了成功舍弃一切,我想在工作之中融入爱好,想在工作之外有自己的生活。

恩,很有道理的一句话,值得每个人来思考这句话。

加油,独立思考人。

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越