Atcoder 的“专属”头文件（AC library）介绍 [不完美的预告] [发现一些错误，准备自爆]

_ACGODs_ · 2025-12-16 21:41:51 · 算法·理论

Atcoder 的“专属”头文件介绍

Flag：新年前做完。

先投一点看看。

概述

大家在打 Atcoder 比赛时可能会遇到如下困难：板子打错死死调不出来、想到了一个好的解法却因为没学过 / 太麻烦了不愿意打而没实现出来。

Atcoder 有一套专属的头文件可以“缓解”这种情况。

这套头文件叫“AC Library”，可以帮助你在 Atcoder 上更好的打比赛。你可以在这里练习和体验 AC Library。

贴错链接是已知问题，不打算修改，比赛就在里面后三个链接里。（20251214）

注意：切勿对该系列头文件产生依赖。

基础使用方法

如果你需要使用该系列的头文件，请在程序开头加入 #include<atcoder/all>（包含所有 AC Library 中的头文件） 或之后的章节中提到的 atcoder/ 目录下的其他头文件。

请导入命名空间 atcoder 或在所有 AC Library 接口的开头加入 atcoder::。

你可能需要的新框架：

#include <atcoder/all>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;
signed main(){
    return 0;
}

注意

以下所有数据结构中的“第 i 个位置”字眼均为原数组上第 i 个位置的值，也就是“a_i”。

下标从 0 开始。

树状数组 / fenwicktree

可以维护单点加和区间和，时间复杂度均为 O(\log n)。

创建

创建：fenwick_tree<T> fw(int n)，表示创建一个树状数组，元素类型为 T，容量为 n。

修改

单点加：fw.add(int i,T x)，表示在第 i 个位置加上 x。

查询

区间和：fw.sum(int l,int r)，表示 [l,r) 区间的和。

线段树 / segtree

本线段树不含懒标记，所以仅支持单点修改和区间查询还有一些二分，若需要区间修改，请移步含懒标记的线段树一章。

该数据结构可以维护一种符合幺半群的运算。
符合幺半群的运算：有一种运算 \text{op}，满足 (a \: \text{op} \: b)\:\text{op}\ c=a\:\text{op}\: (b\:\text{op}\: c) 且有一常量 e，满足对于任何 a，a \: \text{op} \: e=a。

创建

创建：segtree<T,op,e> seg(int n)，表示创建一个线段树，其类型为 T，其运算为 \text{op}，其“常量”为 e，容量为 n。

修改

单点修改：seg.set(int i,T x)，表示将第 i 个位置上的值修改为 x。
提示：单点 \text{op} 可以用该方法实现：seg.set(int i,op(seg.get(i),T x))，将第 i 个位置上的值修改为 i \: \text{op} \: x，注意 seg.get 中的 i 和 seg.set() 中的 i 必须相等。

查询

单点查询：seg.get(int i)，查询第 i 个位置上的值。时间复杂度 O(1)。
区间查询：seg.prod(int l,int r)，查询第 l 到第 r 位置上的操作和。也就是 a_l \: \text{op} \: a_{l+1} \: \text{op} \dots \text{op} \: a_{r-1}。
整体查询：seg.all_prod()，等同于 seg.prod(0, n)。

二分