许多计算机相关专业的人，毕业之后除了为应付面试外，基本都很少再去碰算法。而在实际的产品或者项目开发过程中，大多数人也没有必要亲自去实现复杂的算法。因此，算法渐渐淡出程序员的日常生活。同时，在现实生活中有另外一种声音：程序员的生活太纠结，coding的速度永远跟不上需求变化的速度，提需求的客户似乎成了程序员的“天敌”，成了他们“苦逼”生活的罪魁祸首。

那么，一本讲算法比赛的书跟这又有多少关系呢？就从我自身的经历说起吧。我不是计算机科班出身，但因种种原因进入了这个行业，而且是从一个很低的起点进入的。于是我像所有人一样，平时很难静下心来学习算法，有了面试就去临时抱本书突击一下。终于有一天我受不了了这种循环，我扪心自问：难道只有为了某个急功近利的目的我才愿意去付出自己的时间吗？佛家有句话叫“凡夫求果，菩萨求因”，我就想，既然成不了圣人，就学一回圣人吧。

因缘际会，我接触到了“入门经典”及其作者刘汝佳，于是一发不可收，写这本书的过程也变成了修行与学习的过程。慢慢地，我发现算法对于实际工作的人而言，有着比应付面试更大的价值。所谓的算法、组件、模式，就像是一些基础的原材料，对于优秀的建筑师来说，需要透彻地理解（不一定写得很熟练）它们的关键性。因为一个错误的设计，对于系统来说，所要付出的代价远比一般的程序bug要高得多。更进一步说，现在做软件的为什么苦，为什么抱怨需求变化快？因为解决问题的思维方式出现了偏差。需求分析绝对不是简单地拿着需求，直接翻译成代码—这是最低层次的实现。算法分析的意义，更多地不在于性能，不在于那些脑筋急转弯，而在于发现纷繁复杂的问题背后的“不变式”，而这正是本书要着力与大家分享的地方。

2012年，《算法竞赛入门经典——训练指南》第一版出版面市。时光荏苒，转眼间已过去8年时间。这些年间，竞赛界出现了很多新的知识点和题目类型；另外，在人工智能大潮的感召下，更多的学子参与到了算法竞赛中。为了能够为这些新增的知识点提供一些例题讲解以及习题练习，大概从两年前开始，笔者和刘汝佳老师开始考虑对本书进行增补。

我们对近些年来ACM/ICPC等信息学竞赛中新增的知识和点题型进行了仔细的斟酌和比对，通过多次筛选，挑选出了一些极具代表性的习题，增补到了原书中。这些习题基本都是ACM/ICPC各个区域比赛以及世界总决赛的真题以及各国信息学竞赛中的真题，部分章节中几乎有一半习题被更新为最新题目。

具体来说，《算法竞赛入门经典——训练指南》升级版新增的内容主要有：

第2章，补充了数学部分线性筛、莫比乌斯反演以及积性函数。将FFT放到第2章并且进行了扩写，并且增加了NTT以及FWT相关例题。

第3章，补充了字符串部分，主要是后缀自动机、Manacher字符串相关算法；倍增LCA、点分治、树链剖分等树上经典问题与方法；LCT的相关例题以及习题；离线算法，包括基于时间分治、整体二分、莫队；kd-Tree；可持久化数据结构，包括权值线段树、Trie、树状数组、Treap的可持久化版本。

第4章，补充了一道平面切割立方体的3D几何例题（LA 5808）。

第5章，完善了一些例题题解的描述。

第6章，补充了树分块和树上莫队等内容。

以上新增部分的内容提纲及题解审阅由刘汝佳老师完成，具体的题解及代码编写由陈锋完成。另外，为了提升读者的做题体验感，本书在牛客竞赛网上提供了各章节绝大多数题目的题单（扫描封底“文泉云盘”二维码，获取题单及其他资源下载方式），读者可以获得更好的提交速度以及体验。当然，读者也可以挑选自己薄弱的章节，有针对性地进行题目的练习。