Expand description
データ構造
§セグメント木系の比較
| データ構造 | 新規作成 | 区間更新 | 点更新 | 区間取得 | 点取得 |
|---|---|---|---|---|---|
Segtree | new(n, M) | assign(i, X), update(i, X) | fold(l..r) | ||
DualSegtree | new(n, M) | update(l..r, X) | get(i) | ||
LazySegtree | new(n, A) | update(l..r, X) | fold(l..r) | ||
DynamicSegtree | new(M) | assign(i, X) | fold(l..r) | ||
DynamicDualSegtree | new(M) | update(l..r, X) | get(i) | ||
DynamicLazySegtree | new(A) | update(l..r, X) | fold(l..r) | ||
PersistentSegtree | new(n, M) | assign(i, X) | fold(l..r) | ||
SparseTable | new(s, A) | fold(l..r) | |||
DisjointSparseTable | new(s, S) | fold(l..r) | |||
FenwickTree | new(n, G) | update(i, X) | fold_to(..r), fold(l..r) | ||
SegtreeBeats | new(n) | chmin(l..r, X), chmax(l..r, X), add(l..r, X) | sum(l..r, X) | ||
StarrySkyTree | new(n) | update(l..r, X) | fold(l..r) |
Modules§
- aho_
corasick - Aho-Corasick法
- binary_
trie - 非負整数を2進数として管理する。
- bitset
- 任意サイズのbit列を扱う。
- cht
- Convex Hull Trick
- cumulative_
sum_ 1d - 1次元累積和
- cumulative_
sum_ 2d - 2次元累積和
- disjoint_
sparse_ table - 半群の列の区間取得($O(1)$)ができる。
- dual_
segtree - モノイド列の区間更新・点取得($O(\log n)$, $O(\log n)$)ができる。
- dynamic_
dual_ segtree - 動的双対セグメント木
- dynamic_
lazy_ segtree - 動的遅延セグメント木
- dynamic_
segtree - 動的セグメント木
- fenwick
- 可換群の点更新・区間取得($O(\log n)$, $O(\log n)$)ができる。
- fenwick_
add - 可換な加減算に特化したFenwickTree
- fenwick_
on_ fenwick - Fenwick木上にFenwick木を構築する。
- foldable_
deque - 半群で畳み込み可能なdeque
- integer_
set - Mexを求められるデータ構造
- interval_
heap - 最大値と最小値を得られるヒープ
- lazy_
segtree - モノイド列の区間更新・区間取得($O(\log n)$, $O(\log n)$)ができる。
- lazy_
segtree_ coeff - 係数乗算付き区間加算区間総和遅延セグ木
- lazy_
skew_ heap - 遅延加算付き融合可能ヒープ
- li_chao
- Li-Chao tree
- link_
cut_ tree - Link-Cut Tree
- linked_
list - 連結リスト
- merge_
sort_ tree - Merge-sort Tree
- multiset
- 同一要素を複数個挿入可能な
Set - ordered_
map - 順序付き辞書
- ordered_
set - 順序付き集合
- palindromic_
tree - 回文木
- partially_
persistent_ unionfind - 部分永続UnionFind
- persistent_
array - 永続配列
- persistent_
queue - 永続キュー
- persistent_
segtree - 永続セグメントツリー
- persistent_
stack - 永続スタック
- persistent_
unionfind - 永続UnionFind
- potential_
unionfind - ポテンシャル付きUnionfind
- qword_
tree - 64分木
- range_
search_ tree - 領域内の点を列挙する
- rollbackable_
unionfind - ロールバック可能Unionfind
- rollbackable_
vector - ロールバック可能Vec
- segtree
- モノイド列の点更新・区間取得($O(\log n)$, $O(\log n)$)ができる。
- segtree_
2d - 二次元のセグメント木
- segtree_
beats - Segment Tree Beats
- segtree_
linear_ add - 区間一次関数加算セグメントツリー
- segtree_
linear_ add_ range_ sum - 区間一次関数加算区間総和セグメントツリー
- segtree_
on_ segtree - セグメント木上にセグメント木を構築する。
- skew_
heap - 融合可能ヒープ
- sparse_
table - 冪等性と結合性をもつ列の区間取得($O(1)$)ができる。
- sparse_
table_ 2d - 冪等性と結合性をもつ2次元列の区間取得($O(1)$)ができる。
- splay_
tree - Splay Tree
- starry_
sky_ tree - 区間加算・区間Max(Min)
- starry_
sky_ tree_ count - 区間加算・個数総和付き区間Max(Min)
- succinct_
bitvec - 簡潔ビットベクトル
- trie
- Trie木
- unionfind
- 素集合データ構造
- usize_
set usizeを用いた集合表現- wavelet_
matrix - Wavelet matrix