7K12 blog

猫でも分かる何か

ライブラリ

graph

https://9871225.hatenablog.com/entry/2021/11/25/232020

単一始点から全ての終点までの最短経路を求める O((V+E) \log V)
https://9871225.hatenablog.com/entry/2022/05/22/225011

  • 強連結成分分解 LIB::StronglyConnectedComponents

互いに行き来できる頂点集合に分解する O(v+e)
https://9871225.hatenablog.com/entry/2023/10/20/072527

  • HL分解 LIB::HeavyLightDecomposition

セグ木などのデータ構造と併用することでパスクエリを O(\log^2{n}) で処理する
https://9871225.hatenablog.com/entry/2023/09/08/070307

  • グリッドグラフ変換 GridGraph

https://9871225.hatenablog.com/entry/2023/12/16/083237

  • 全方位木DP LIB::RerootingDP

https://9871225.hatenablog.com/entry/2023/11/04/052046

data structure

  • いもす法 LIB::Imos

区間加算 O(1)、区間和取得 O(1)、更新処理 O(N)
https://9871225.hatenablog.com/entry/2021/06/27/111610

  • 遅延セグメント木 NyaaLIB::DS_LazySegmentTree

任意区間のクエリを O(\log N) で処理する
https://9871225.hatenablog.com/entry/2021/07/21/224900

  • ウェーブレット行列 LIB::WaveletMatrix

任意区間のk番目の要素や要素xの個数を O(\log V) で取得する
https://9871225.hatenablog.com/entry/2022/04/10/013704

  • 複合コンテナ CompoundContainer

https://9871225.hatenablog.com/entry/2023/12/12/080903

nyaa

  • 形式的冪級数 LIB::FormalPowerSeries

多項式の乗除算 O(k \log k) (k=n+m)
https://9871225.hatenablog.com/entry/2023/09/26/204025

  • ローリングハッシュ LIB::RollingHash

文字列検索 O(N+M)
https://9871225.hatenablog.com/entry/2023/08/11/015550

  • めぐる式二分探索

https://9871225.hatenablog.com/entry/2023/11/10/012139

  • mod型ライブラリ LIB::ModINT

https://9871225.hatenablog.com/entry/2022/03/02/095746

  • 尺取法 auto tpt

https://9871225.hatenablog.com/entry/2023/03/24/153655

  • LIB::AhriSet

multiset に標準コンテナの頻出関数を全部実装した欲張りデータ構造
https://9871225.hatenablog.com/entry/2021/07/28/104146

  • 二次元の回転 auto vvrot

https://9871225.hatenablog.com/entry/2023/06/10/065919

  • データ構造の分割 LIB::MultiSplit

データ構造を O(n \log n) で複数区間に分割する
https://9871225.hatenablog.com/entry/2023/11/24/064900

  • 文字からインデックスを取得する LIB::CharIndex

https://9871225.hatenablog.com/entry/2022/11/18/221707

  • 文字列の複数分割 auto string_split

https://9871225.hatenablog.com/entry/2022/11/05/063308

https://9871225.hatenablog.com/entry/2022/04/20/152634

  • 幾何ライブラリ

https://9871225.hatenablog.com/entry/2023/01/28/010006

  • NyaaLIB_NTL　（NTライブラリまとめ）

素数判定 (IsPrime)、素数列挙 (PrimeTable)
https://9871225.hatenablog.com/entry/2022/05/12/145950

  • NyaaLIB::DS_NyaaImos2D　（二次元いもす法）

矩形区間加算処理 O(1) 矩形区間総和取得処理 O(1) 累積和の更新 O(HW)
https://9871225.hatenablog.com/entry/2021/06/27/121846

  • NyaaLIB::DS_NyaaBIT　（フェニック木 Binary Indexed Tree）

要素加算 O(\log N) 区間加算 O(\log N)
https://9871225.hatenablog.com/entry/2021/07/07/053745

  • NyaaLIB::DS_UnionFind　（素集合データ構造） O(\log N)

https://9871225.hatenablog.com/entry/2022/03/02/202403

  • NyaaLIB::GT_GridGraph　（グリッドをグラフに変換）

https://9871225.hatenablog.com/entry/2022/05/21/193058

  • NyaaLIB::GT_NyaaLCA　（木の最近共通祖先 Lowest Common Ancestor）

前処理 O(N \log N) 共通祖先・木の頂点間距離・パス上に存在する頂点 O(\log N)
https://9871225.hatenablog.com/entry/2021/10/19/021617

https://9871225.hatenablog.com/entry/2022/03/17/205743


クリエイティブ・コモンズ・ライセンス
この 作品 は クリエイティブ・コモンズ 表示 4.0 国際 ライセンスの下に提供されています。