「观前提醒」 「文章仅供学习和参考，如有问题请在评论区提出」 目录 定义 性质 计算公式推导 求欧拉函数 分解质因子法 筛法求欧拉函数 参考资料 定义 欧拉函数的符号表示是\(\varphi(n)\)，表示\(1\simn\)中和\(n\)互质的数的个数。 例如，\(\varphi(12)=4\)，即\(1,5,7,11\)。 性质 若\(n\)是质数，则\(\varphi(n)=n1\)。 质数会和小于它本身的所有正整数互质，即\(n\)与\(1\simn1\)中所有数互质。 当\(n\)是奇数时，\(\varphi(2n)=\varphi(n)\...

「观前提醒」 「文章仅供学习和参考，如有问题请在评论区提出」 目录 O(N)建树 方法一 方法二 维护区间和 单点修改，区间查询 区间修改，单点查询 区间修改，区间查询 维护二维子矩阵和（二维树状数组） 单点修改，子矩阵查询 子矩阵修改，单点查询 子矩阵修改，子矩阵查询 求逆序对个数 求数列中小于x的元素个数 参考资料 这里主要讲树状数组的各种扩展应用，至于树状数组的具体实现原理可以看下面的博客。 树状数组Oneway`博客园 O(N)建树 对于树状数组最基本的建树方式，就是每个点加值。 时间复杂度：\(O(NlogN)\) 代码实现 inttr[N]...

「观前提醒」 「文章仅供学习和参考，如有问题请在评论区提出」 目录 引入 基本原理 建树 区间查询 单点修改 区间修改+懒惰标记 例题 P3372【模板】线段树1洛谷 P3373【模板】线段树2洛谷 小结 参考资料 引入 线段树（SegmentTree）是算法竞赛中常用的用来维护区间信息的数据结构。 线段树可以在\(O(logN)\)的时间复杂度内实现单点修改、区间修改、区间查询等操作。能够用来维护很多类型的信息，包括但不仅限于求区间和、求区间最值、求区间最大子段和、求区间最大公约数等。 基本原理 这里先给出线段树的结构图， 从结构图我们可以看到，线段树是一颗...

「观前提醒」 「文章仅供学习和参考，如有问题请在评论区提出」 目录 前言 定义 性质 求LCA 倍增算法 Trajan算法 树链剖分 基本概念 基本性质 具体实现 参考资料 前言 简单的模板整理，只是概括了一下具体的实现方法（说到底是给自己写的），如果看不明白可以去看原视频（讲的很好），链接在参考资料里。 定义 最近公共祖先简称\(LCA\)（LowestCommonAncestor）。在一个树上，两个节点的最近公共祖先，就是这两个点的公共祖先里，离树根最远的那个。 例如，\(6\)与\(8\)的最近公共祖先为\(1\)，\(5\)和\(3\)的最近公共祖先...

「观前提醒」 「文章仅供学习和参考，如有问题请在评论区提出」 目录 引入 Atlantis问题（矩形面积问题） P5490【模板】扫描线洛谷 二维数点 P2163园丁的烦恼洛谷 PairSumandPerfectSquare 参考资料 一些扫描线问题的整理。 引入 扫描线一般被用来解决一些图形问题，像图形面积、周长，以及二维数点问题等。 Atlantis问题（矩形面积问题） 在二维坐标系上，给出多个矩形的左下和右上坐标\((x1,y1),(x2,y2)\)，求出所有矩形构成的图形的面积。 观察上面的图形，我们可以通过扫描线来把它分成不同的小矩形，...

观前提醒：「文章仅供学习和参考，如有问题请在评论区提出」 目录 前置 剩余类（同余类） 完全剩余系（完系） 简化剩余系（缩系） 欧拉函数 欧拉定理 扩展欧拉定理 参考资料 前置 剩余类（同余类） 给定一个正整数\(n\)，把所有的整数根据模\(n\)的余数\(r\in[0,n1]\)分为\(n\)类，每一类就可以被表示为\(C_{r}=nx+r\)。那么这类数所构成的集合就称为模\(n\)的剩余类。 完全剩余系（完系） 给定一个正整数\(n\)，有\(n\)个不同的模\(n\)的剩余类（因为余数\(r\in[0,n1]\)）。 从这\(n\)个不同的剩余类中各...