线段树 II 之 懒惰标记 前置知识：线段树 I – ztr 的小窝 (ztrztr.top) 懒惰标志 Lazy Tag 懒惰标志，是维持线段树的区间修改查询的复杂度在 $O(\log n)$ 级别的一个方法。 正常的区间修改查询的复杂度可以说是 $O(n)$ 级别的，因为每次修改一个，需要一直传到叶子节点为止。 但是我们发现，如果这样的话，修改…

01-Trie ‍ 如果不理解 Trie 树的可以看我的之前的文章 Trie 树 – ztr 的小窝 (ztrztr.top)。 01 Trie 树，是运用 Trie 的思想储存一些数，从而实现省空间。 实现 01 Trie 树，是把原本是字符串中的都换成了一个数的二进制串。 对于添加数的操作，我们把数按二进制把二进制中的每一位拆分，然后按 Tri…

Trie 树 Trie 树是一种可以快速查找一个字符串是不是在目前集合中的一个数据结构。 Trie 树的中文名是字典树，顾名思义，这个数据结构就是一个长得像字典的树。 思路 ​​ 上面这个图就是一个 Trie 树，这种树是一个有根树。这种数据结构中，我们不再把每个字符串完全分开存储，而是把相同的合并了。 插入 我们从根节点开始，检查根节点的边有没有…

拓扑排序与关键路径的学习笔记。

拓扑排序的介绍。

欧拉回路和欧拉路径的总结

线段树是一种可以维护区间修改和查询的树形数据结构。

BFS、DFS 和图的储存与最短路算法。

LCA 是最近公共祖先的简称。 朴素算法 如果两个点的深度相同：就往上跳，直到两个节点相同。 否则先让两个点的深度相同。 倍增 和朴素算法类似，只是把挨个往上跳变成每次跳 $2^i$。 代码： #include <bits/stdc++.h> using namespace std; /* */ int n, m, s; vector …

算法标签：==贪心== ==图论== Kruskal 算法思路 这个算法主要是运用了贪心思想。 首先对每个边进行排序，每次选取最小的边，用并查集判断是否选过或形成环。 当边选够了，输出。 注意事项 结束循环的条件有两种： ++ cnt >= n - 1：这时候注意 sum += edge[i].value 在判断的前面，因为判断的意义是：到现…