迪杰斯特拉算法
迪杰斯特拉算法 介绍 Dijkstra 算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解非负权图上单源最短路径的算法。 图示 实现 Dijkstra...
树状数组
树状数组 介绍 树状数组多用于单点修改和区间查询，是一种代码量小的数据结构，扩展数据结构为线段树。 图示 最下面的八个方块代表原始数据数组 a。上面参差不齐的方块（与最上面的八个方块是同一个数组）代表数组 a 的上级——c 数组，即树状数组结构。 c 数组就是用来储存原始数组 a 某段区间的和的，也就是说，这些区间的信息是已知的，我们的目标就是把查询前缀拆成这些小区间。 例如，从图中可以看出： c2c_2c2 管辖的是 a[1…2]a[1 \ldots 2]a[1…2]； c4c_4c4 管辖的是 a[1…4]a[1 \ldots 4]a[1…4]； c6c_6c6 管辖的是 a[5…6]a[5 \ldots 6]a[5…6]； c8c_8c8 管辖的是 a[1…8]a[1 \ldots 8]a[1…8]； 剩下的 c[x] 管辖的都是 a[x] 自己（可以看做 a[x…x]a[x \ldots x]a[x…x] 的长度为 1 的小区间）。 lowbit函数 例如，欲查询 a...
并查集
并查集 介绍 并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 顾名思义，并查集支持两种操作： 合并（Union）：合并两个元素所属集合（合并对应的树） 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合 并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。 算法示例 原始并查集 123456789101112131415161718192021class Disjointset{ public: Disjointset(int n):parent(n+1){ for(int i=1;i<=n;++i){ parent[i] = i; } } int Find(int index){ return parent[index]==index?parent[index] :...
快速幂
快速幂 介绍 快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 O(logn\log nlogn) 的时间内计算 ana^nan 的小技巧，而暴力的计算需要 O(nnn) 的时间。 计算 a 的 n 次方表示将 n 个 a 乘在一起： an=a×a⋯×a⏟n 个 aa^{n} = \underbrace{a \times a \cdots \times a}_{n\text{ 个 a}}an=n 个 aa×a⋯×a。然而当 a,n 太大的时侯，这种方法就不太适用了。不过我们知道：ab+c=ab⋅ac, a2b=ab⋅ab=(ab)2a^{b+c} = a^b \cdot a^c,\,\,a^{2b} = a^b \cdot a^b = (a^b)^2ab+c=ab⋅ac,a2b=ab⋅ab=(ab)2。二进制取幂的想法是，我们将取幂的任务按照指数的二进制表示来分割成更小的任务。 算法示例 12345678910111213141516long long int quik_power(int base, int...
摩尔选举求众数
摩尔选举求众数 介绍 博耶-摩尔多数投票算法（Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间复杂度、线性时间复杂度算法。这一算法由罗伯特·S·博耶和J·斯特罗瑟·摩尔在1981年发表，也是处理数据流的一种典型算法。 图示 x轴为计数器中存储的元素，而下方y轴为输入的元素序列。遇到相同元素或者计数器中没有元素，计数器加入重复元素，如果遇到不同元素计数器消除一个元素。 算法示例 123456789int majorityElement(vector<int>& nums) { int cnt = 0, now = nums[0], n = nums.size(); for (int i = 0; i < n; i++){ if(cnt == 0) now = nums[i]; else if(now == nums[i]) cnt++; else cnt--; ...
