《算法笔记》是一本很好的算法书籍，适合计算机专业研究生入学考试复试上机、各类算法等级考试（如PAT、CSP等）的辅导，书中涵盖了C/C++快速入门、入门模拟、算法初步、C++标准模板库等内容，对学习C语言、数据结构与算法的入门非常有帮助，该书内容丰富，讲解清晰，代码示例详细，能够帮助读者理解算法的原理和实现方法，无论是准备考试还是学习算法基础知识，这本书都是一本值得推荐的入门辅导书。
内容介绍
这是一本零基础就能读懂的算法书籍，读者不需要因为自己没有语言基础而畏惧。书籍的第2章便是一个C语言的入门教程，内容非常易懂，并且十分实用，阅读完这章就可以对本书需要的C语言基础有一个较好的掌握。
本书已经覆盖了大部分基础经典算法，不仅可以作为考研机试和PAT的学习教材，对其他的一些算法考试（例如CCF的CSP考试）或者考研初试的数据结构科目的学习和理解也很有帮助，甚至仅仅想学习经典算法的读者也能从本书中学到许多知识，本书还有配套的《算法笔记上机训练实战指南》
本书的作者是同样经历过考研机试和各类算法考试的专家型学长，知晓这类考试中的痛点，以及考生在学习算法时容易产生困惑的地方，因此可以把本书看作是学长为你奉献的满满的经验干货，这是有价值的东西。
本书的试印版本献给了浙大考研学子，并令当年的浙大考研机试平均分增加了十多分，收获了考生的大量好评。但作者并没有止步于此，经过了半年多时间的内容完善和补充之后，新的版本在新一年的考研机试中再次获得了考生的一致赞美。最后，在经过精心整理之后，书籍终于定稿，并编撰成书。
我们知道，纸质书籍的一个弱点就在于不能像软件一样随时更新内容，但本书采用了与二维码相结合的方式，使得本书变为能够随时更新内容的书籍，读者也可以随时从二维码中找到勘误。这种作者和读者能够相互沟通的方式让书籍变“活”了，也能够帮助提升读者对知识的理解。
目录
- 第1章 如何使用本书 1
- 第2章 C/C++快速入门 5
- 第3章 入门篇（1）——入门模拟 85
- 第4章 入门篇（2）——算法初步 99
- 第5章 入门篇（3）——数学问题 152
- 第6章 C++标准模板库（STL）介绍 191
- 第7章 提高篇（1）——数据结构专题（1） 245
- 第8章 提高篇（2）——搜索专题 269
- 第9章 提高篇（3）——数据结构专题（2） 283
- 第10章 提高篇（4）——图算法专题 347
- 第11章 提高篇（5）——动态规划专题 425
- 第12章 提高篇（6）——字符串专题 449
- 第13章 专题扩展 465
- 参考文献 481
树的遍历 树既然具有二维性，一个重要的课题就是将二维转换为一维，也就是树的遍历。树的遍历总共分为三种，前序遍历，中序遍历和后序遍历。这里的前，中和后都是说的根，也就是根遍历的顺序。实际上在树的遍历中，永远是先左节点，后右节点的。但是关键是根节点。如果先是根节点，然后左节点，最后右节点，就是前序遍历，也就是根在前面遍历。如果先是左节点，然后根节点，最后右节点，就是中序遍历，也就是根在中间遍历。如果先是左节点，然后右节点，最后根节点，就是后序遍历，也就是根在最后遍历。 树的三种遍历方式，可以将二维的树，转换为一维的数组。前序，中序和后序是树的一维形态。二维可以转换为一维，那么一维是否可以转换为二维呢？这实际上就是一个面试题，我们将在下面详细分析。
树的特点 树和链表相对比，会更加复杂一些。实际上链表中节点有一个指针指向下一个节点，而在树中，有两个指针，分别指向左，右两个孩子节点。这种对应关系，就不是链表中的一对一了，在树中，对应关系就是一对多了。如果说链表可以理解为一维的世界，则树就是二维的世界了。特别的，树这个二维世界有一个非常重要的节点就是根节点，这个节点可以认为是树的特征节点。因此解决树的问题，找准根节点是非常重要。 在23种设计模式中，组合模式就是运用了树这种数据结构。组合模式的意思就是操作树根这一个元素，好像同时操作整个树一样。在实际的应用中，树可以理解为一种层级结构，比如界面，windows可能是树根，树根会有视图，视图又可分为用户自定义的各种视图控件，整个的ui界面，可以理解为一棵完整的树，而操作树根，比如windows接收到了点击事件，就可以将这个事件分发给这课树的所有节点。这就是组合模式。 树的一个重要的特点，就是有一定的递归性，因此，在解决树相关的问题时，递归的方法，显然是首选。另外，结合树中最重要的要点，就是找到树的特征也就是树根。把握好这两个方面，很多树相关的问题就可以解决了。
莫队算法 首先，orz hzwer 莫队算法是离线处理不带修改的区间询问的算法，效率nsqrt(n) 其实说到底也就是先对询问按一种顺序排个序，然后直接模拟处理的算法。但是因为是按照一定顺序做询问，所以有办法证明算法复杂度是nlogn 首先，把n个元素分为sqrt(n)块，每块有sqrt(n)个元素。然后我们以询问的左端点所在的块的编号为第一关键字，以右端点为第二关键字排序。 一开始我们用两个指针l=1,r=0来表示当前我们已经记录的区间。然后按照排完的顺序依次处理询问。 以bzoj3781为例： 题意是给定一个序列a，每次对于询问[l,r]，输出Σc[i]^2，其中c[i]表示在区间[l,r]中i出现的次数 那么先考虑模拟的做法： 当前我们做到了[x,y]，现在已知在区间[x,y]中的c[i]，以及ans=Σc[i]^2。那么如何可以从c[i]以及x,y,ans继续转移呢？ 我们现在要求[x,y+1]的ans了。那么[x,y+1]的答案比[x,y]多的就是a[y+1]对整个区间的贡献。只要加上a[y+1]带来的贡献就可以了。 只需要y++ --> ans-=c[y]^2 --> c[y]++ --> ans+=c[y]^2 就可以做到从区间[x,y]转移到[x,y+1]了。 那么如果我们现在要求[x,y-1]的ans，只需在原来的ans中扣掉a[y]带来的贡献。 只需要ans-=c[y]^2 --> c[y--] --> ans+=c[y]^2 --> y-- 就可以从[x,y]转移到[x,y-1] 那么[x+1,y]和[x-1,y]就是同理了 这样我们就可以从[x,y]转移到任意的[x',y']了 但是为什么按着这样的顺序模拟就不会T呢？ 在此引用黄巨大的话： 考虑第i个询问和第i+1个询问之间的关系： 一、i与i+1在同一块内，r单调递增，所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。 二、i与i+1跨越一块，r最多变化n，由于有n^0.5块，所以这一部分时间复杂度是n^1.5 三、i与i+1在同一块内时变化不超过n^0.5，跨越一块也不会超过2*n^0.5，不妨看作是n^0.5。由于有n个数，所以时间复杂度是n^1.5 于是就变成了O(n^1.5)了