AtCoder Library（ACL）は AtCoder側で様々なアルゴリズムを実装したものです。
C++で使えます。

詳しくは以下の投稿を見てください。

この記事では、この AtCoder Library にはどのようなアルゴリズムが実装されていて、それはどのように使えばよいのか、ということを解説していきます。

なお、今回の記事では、 AtCoder Library の使い方を確認できる問題が揃えられている、

というものも用いていきます。
このコンテストは、けんちょんさん(@drken) が解説されています。

AtCoder Library は、

#include <atcoder/all>

で一括includeできます。

DSU

無向グラフにおいて、

辺を追加する
2頂点が連結化を判定する

処理を、ならし$O(\alpha (n))$ で行えます。
また、各連結成分が代表となる頂点を1つ持っています。

ならしとは

こちらの記事で詳しく解説されています。

https://rsk0315.hatenablog.com/entry/2022/07/22/090000

コンストラクタ

dsu d(n)

$n \ (0 \leq n \leq 10^8)$個の頂点で辺は$0$個の無向グラフを生成します。
(d というのは、無向グラフの名称です。)

計算量は、 $O(n)$ です。

merge

d.merge(a, b)

頂点$a$と頂点$b$ を辺$(a, b)$ で連結させます。$(0 \leq a,b < n)$
int型で、代表元を返します。

計算量は、ならし$O(\alpha (n))$ です。

same

d.same(a, b)

頂点$a,b$ が連結ならtrueを、そうでないならfalseを返します。$(0 \leqq a, b < n)$

計算量は、ならし$O(\alpha (n))$ です。

leader

d.leader(a)

頂点$a$を含む連結成分の代表元をint型で返します。 $(0 \leq a < n)$

計算量は、ならし$O(\alpha (n))$ です。

size

d.size(a)

頂点$a$を含む連結成分に、いくつ点が繋がっているかをint型で返します。$(0 \leq a < n)$

計算量は、ならし$O(\alpha (n))$ です。

groups

d.groups()

グラフを連結成分ごとに分け、その情報を vector<vector<int>> で返します。

計算量は、$O(n)$ です。

例えば、上のようなグラフでは、 0と1、2と3 が連結していて、連結成分は2つあります。

その場合、vector<vector<int>> で、{{0, 1}, {2, 3}} が返ってきます。

A - Disjoint Set Union

正答例

#include <bits/stdc++.h>
#include <atcoder/all> //読み込む
using namespace std;
using namespace atcoder;
//Created by karaju.

signed main(void){
  int n, q;
  cin >> n >> q;
  dsu d(n);
  //n頂点0辺の無向グラフを生成
  
  for(int i = 0; i < q; i++){
    int a, u, v;
    cin >> a >> u >> v;
    
    if(a == 0){
      d.merge(u, v); //連結させる
    }
    else{
      if(d.same(u, v)){ //もし連結なら
        cout << 1 << endl;
      }
      else{
        cout << 0 << endl;
      }
    }
  }
}

Fenwick Tree

長さ$N$の配列に対して、

1つの要素を変更する
区間の要素の総和を求める

ことが$O(\log N)$ でできるデータ構造です。

コンストラクタ

fenwick_tree<int> fw(n)

長さ$n (0 \leq n \leq 10^8)$で初期値が$0$の配列を生成します。

計算量は、$O(n)$ です。

add

fw.add(p, x);

a[p] に $x$ を加えます。 $(0 \leq p < n)$

計算量は、$O(\log n)$ です。

sum

fw.sum(l, r)

a[l] から a[r - 1] までの総和を求めます。

計算量は、$O(\log n)$ です。

B - Fenwick Tree

正答例

#include <bits/stdc++.h>
#include <atcoder/all> //読み込む
using namespace std;
using namespace atcoder;
//Created by karaju.

signed main(void){
  int n, q;
  cin >> n >> q;
  fenwick_tree<long long> fw(n); //配列作成
  
  for(int i = 0; i < n; i++){
    int a;
    cin >> a;
    fw.add(i, a); //数列を用意
  }
  
  for(int i = 0; i < q; i++){
    int t;
    cin >> t;
    if(t == 0){
      int p, x;
      cin >> p >> x;
      fw.add(p, x); //xを加える
    }
    else{
      int l, r;
      cin >> l >> r;
      cout << fw.sum(l, r) << endl;
    }
  }
}

仕組み

https://algo-logic.info/binary-indexed-tree/

というページにまとめられています。

未完成ですが、記事の引用が必要となったので公開。