算法模板
2022/6/20 5:20:21
本文主要是介绍算法模板,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法模板
数论
//最大公约数 LL gcd(LL a, LL b) { return b ? a : gcd(b, a%b); }
统计
并查集
struct UF{ int n; int cnt; vector<int> fa; vector<int> sz; UF(int _n) : n(_n), cnt(_n), fa(_n), sz(_n, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } bool merge(int x, int y) { int fx = find(x); int fy = find(y); if (fx == fy) return false; if (sz[fx] < sz[fy]) swap(fx, fy); fa[fy] = fx; sz[fx] += sz[fy]; cnt--; return true; } bool connected(int x, int y) { int fx = find(x); int fy = find(y); return (fx == fy); };
树状数组
struct BIT { vector<long long> tree; BIT(int n): tree(n+1){} static constexpr int lowbit(int x) { return x & (-x); } void update(int index, int delta) { // x是从1开始的下标 for (int i = index; i < tree.size(); i += lowbit(i)) { tree[i] += delta; } } //查询区间(0,x)的和 long long query(int x) { long long res = 0; // 从右到左查询,最小到1,不能等于0 for (int i = x; i > 0; i -= lowbit(i)) { res += tree[i]; } return res; } // 查询区间[l, r]的和 long long query(int l, int r) { return query(r+1) - query(l); } };
这篇关于算法模板的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?