OI - Start —— OIer的好帮手

项目地址

警告

为了比赛公平性，禁止在任何竞赛中使用本项目！！！

项目介绍：

你有没有苦于线段树、平衡树、图论等等各种各样的知识点记不清？OI-Start 或许可以帮助你。

OI-Start 为各位 OIer 封装了各种在 OI 中常用的数据结构、实用函数和算法，像 STL 一样开箱即用，十分方便。

使用说明：

1. 珂朵莉树（ODT）

操作：

ODT odt;          // 定义
odt.init(1, 1e9, 0);     // 初始化区间[1,1e9]值为0 
odt.assign(3, 50000, 1); // [3,50000]赋值为1
// 操作符：+ - * /
odt.update(10, 10000, 2, '+'); // [10,10000]每个数+2
odt.update(50, 200, 3, '*');    // [50,200]每个数*3
int sum = odt.query(30, 700, '+'); // 返回[30,700]区间和（第三个参数支持四则运算符 + - * /）

2. 线段树（Seg）

Seg<大小> seg;
seg.build(建树的原数组, 建的左区间, 建的右区间, 根节点);
seg.update(目标修改区间的左边界, 目标修改区间的右边界, 修改值, 操作类型(+ - * /), 当前节点区间左边界, 当前节点区间右边界, 当前节点存储下标);
// 当前节点区间左边界, 当前节点区间右边界, 当前节点存储下标 可不写
seg.query(); // 参数与 update 相同

3. FastIO

int a, b;
in >> a >> b;
out << a + b;

注意：每次读入完成后，Windows 下请 Ctrl + Z，Linux 下 Ctrl + D 手动读入 EOF 以结束读入！

4. 并查集（UF）

UF<大小> uf;
uf.init();       // 初始化
uf.merage(x, y); // 合并 x y 的集合
uf.query(x, y);  // 检查是否连通

5. 实用函数库（funct）

快速幂

funct tools;
int a = tools.power(x, y);     // a = x ^ y
int b = tools.power(x, y, mod);// b = x ^ y % mod

进制转换

funct tools;
string s = conversion(x, n); // 把十进制数n转换成x进制的数，返回字符串
int k = conversion(x, s);    // 把x进制的数转换为10进制的数，s是字符串

lcm

funct tools;
int a = tools.lcm(x, y); // 返回 x y 的 lcm 值

判断质数

funct tools;
int a = tools.prime(x); // 如果 x 为质数，返回1，否则返回0

6. 树状数组 (BIT)

1. 单点修改, 区间查询

BIT<大小> bit;     // 定义
bit.update(x, k);  // 将第x个数加上k
int a = bit.query(x); // 查询x的前缀和，即[1, x]区间的值

当前支持内容：

• 数据结构

  • ODT
  • 线段树
  • 树状数组
  • 字典树

• 杂项

  • FastIO
  • 实用小函数

未来支持内容：

• 数据结构

  • 图专项
  • 普通平衡树
  • 树链剖分

• 杂项

  • 高精库

后记

如何贡献代码

fork 我的仓库并修改后，提交 PR 请求

怎么报告问题

提交 issues 即可

欢迎各位为 OI-Start 贡献代码！

给孩子点个 Star 吧