划水_小星

基础算法小结

python代码实例学习(2) 未归档(3) 爬虫学习(14) 题解(11)

/ 注册

全部文章 / 基础算法小结（共5篇）

单调栈

单调栈是一种和单调队列类似的数据结构。单调队列主要用于解决滑动窗口问题，单调栈则主要用于解决NGE问题（Next Greater Element），也就是，对序列中每个元素，找到下一个比它大的元素。（当然，“下一个”可以换成“上一个”，“比它大”也可以换成“比他小”，原理不变。）我们维护...

单调栈

2021-03-16

1 587

ST表

ST表（Sparse Table，稀疏表）是一种简单的数据结构，主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。 //进行预处理，计算区间最大值 int f[MAXN][21]; // 第二维的大小根据数据范围决定，不小于log(MAXN) f...

ST表

2021-03-15

0 390

LCA

1、倍增算法 #include<bits/stdc++.h> #define MXN 50007 using namespace std; std::vector v[MXN];//图 std::vector w[MXN];//边权 int fa[MXN][31], cost[MXN][...

LAC 倍增

2021-01-01

0 338

树状数组

树状数组（Binary Index Tree, BIT）。最简单的树状数组支持两种操作，时间复杂度均为：单点修改：更改数组中一个元素的值区间查询：查询一个区间内所有元素的和 1.lowbit(x) lowbit(x) = ((x)&(-x))此操作为取x在二进制下的最后一位1（数字在计算...

树状数组

2020-11-04

0 448

并查集

并查集并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：合并（Union）：把两个不相交的集合合并为一个集合。查询（Find）：查询两个元素是否在同一个集合中。初始化： fa[i]=i;Find: 无压缩 int Find(int x) { if(fa[x]...

并查集

2020-10-13

0 507