小猫咪吃python

# 前置知识 线段树 (上)，线段树 (下)，字典树 # 可持久化的数据结构 “可持久化” 指数据结构可以缓存其历史任意时刻的状态（参考 git 可以记录代码任意时刻是什么样的，并且也可以回滚到历史任意时刻）。 换言之，可持久化数据结构高效的记录该数据结构所有的里是状态。 要注意的是，并非 所有的数据结构都是 可持久化的。只有在操作的时候 数据结构整体 不会发生变化...

# 字典树 字典树：高效的 存储 和 查找 字符串集合 的基础数据结构，又叫 Trie 树、前缀树等。 # 字典树的结构 假设现在有一个问题是这样的： 给出一个单词序列，再给出一个单词，查找该单词 是否 在序列中出现过。 例如：给出单词序列为： [apple, app, able, abc] 给出的单词为 and ，那么结果应该是 False ；给出单词为 able ，那么结果应该是 True ； # 暴力思路分析 暴力思路很简单，我们只需要先遍历单词序列中的每个单词，对于每个单词，都判断一下...

# 前置知识 接前文：看完必会的线段树攻略 2.0（上）。 在前文中，着重讲解了线段树的 单点修改 和 区间查询两个操作，并没有涉及到区间修改，因此在本文中将之补充。 # 线段树 简单回顾一下前文的内容。 在单点修改中，使用的方法是先找到这个元素所在的叶子节点，从叶子节点 pushup 一遍，更新 它的所有祖先节点。而这个 pushup 操作，因为要从叶子节点更新到根节点，所以该操作是和树高度成正比的，因此时间复杂度是 O(logn) 。 如果延续单点修改的思路到区间修改，假设需要修改的区间有 n 个元素，那么时间复杂度将会来到 O(nlogn)...

# 前置知识 初始版本是这个：神奇的线段树（上），初始版本中的攻略并不完全，没有懒标记部分，因此在本文（2.0 版本）中，将更新更详细的讲解，以及时间复杂度的证明，补充懒标记部分。 # 线段树 线段树是一种基于分治思想的二叉树结构，用于在区间上进行信息统计。 # 那么线段树长什么样子呢？ 线段树上的每一个节点都代表着一个区间； 线段树的根节点代表着最大的统计范围； 线段树的每一个叶结点的长度都是 1，也就是唯一值； 对于每个内部节点 [L,R] ，它的左子节点都是 [L,mid] ，右子节点都是 [mid+1,R] ，其中 mid 的值为 mid=(L+R)/2...

# 前置知识 树状数组的基本思路和简单实现，对树状数组不了解，需要先看这篇入门，本文的题目承接这篇文章。 # AcWing 241. 楼兰图腾 在完成了分配任务之后，西部 314 来到了楼兰古城的西部。 相传很久以前这片土地上 (比楼兰古城还早) 生活着两个部落，一个部落崇拜尖刀 (V)，一个部落崇拜铁锹 (∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。 西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 n 个点，经测量发现这 n 个点的水平位置和竖直位置是两两不同的。 西部 314 认为这幅壁画所包含的信息与这 n...

# 前置知识 lowbit(x) ：元素 x 在二进制表示下，其最低位的 1 和 后面的所有 0 构成的数。 比如：当 x=12 的时候，x 的二进制表示为 1100 ，那么它最低位的 1 和后面所有 0 构成的数二进制表示为 [100]、十进制是 4，所以 lowbit(12)=4 。 int lowbit(int x) { return x & -x;}# 树状数组 树状数组主要应用场景是给出一个长度为 n 的数组，对数组做如下两种操作： 输出区间 [l,r] 所有数的和。 将给出数组的第 i 个数加上...

# 前置知识 看完必会的并查集入门攻略。本文是上篇文章的延伸，并查集的实战应用篇。 目录 AcWing 1250. 格子游戏：二维坐标的并查集裸替，主要考察二维坐标转一维。 AcWing 1252. 搭配购买：使用并查集把相同集合的多个物品看做一个整体，方便使用 01 背包。 AcWing 237. 程序自动分析：带有离散化的并查集。 AcWing 238. 银河英雄传说：维护额外信息（距离和个数）的并查集。 AcWing 239. 奇偶游戏：综合应用。带有边权的并查集和带有扩展域的并查集，同时也应用了离散化。 # AcWing 1250. 格子游戏 Alice 和 Bob...

并查集是一种思路巧妙，代码很短的数据结构，也因此常常在算法题或者面试中出现。下面我们以一个模板题目作为示例，详细描述并查集的基本原理及使用。 # AcWing 836. 合并集合 一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。 现在要进行 m 个操作，操作共有两种： M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作； Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中； 输入格式 第一行输入整数 n 和 m。 接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b...

本次推荐的书应该比较小众（指看过的人不多），是由知乎出品的一本心理学范围的书，各大平台均可购买。书名叫做《不要挑战人性》，作者是潘楷文老师。书的副标题是 “史上 20...

# 前置知识 差分约束问题的常规思路 # 拓扑排序 对于一个图，图中所有的点可以构成一个序列，对于图中的每条边 x->y ，在序列中 x 都出现在 y 的前面，则称这个序列是这个图的拓扑序列，这个图是拓扑图。 也就是说，当用拓扑排序排好之后，整个图中的边都是从前往后的。 例如下图中，可以组成一个序列 [1,2,3] ，其中三条边 1->2 ， 2->3 ， 1->3 。均是由前面的点指向后面的点。 如果把边 1->3 变成 3->1 ，那么图中就会出现环，而边 3->1...