README.md

data_structure

Big Integer

bigint.hpp
多倍長整数(simple multiplication, FFT, karatsuba)

• Bigint (0以上の数のみ)
  verify: AOJ(National Budget)
  verify: AOJ(Addition of Big Integers)
  verify: AOJ(Difference of Big Integers)
  verify: AOJ(Multiplication of Big Integers)
  verify: AOJ(Division of Big Integers)
  verify: AOJ(Reminder of Big Integers)
  verify: AOJ(Multiplication of Big Integers II)

Binary Indexed Tree

binary_indexed_tree.hpp
端からの和の取得, 一点への加算がO(logN)でできるデータ構造
2次元版は更新がある時のみ使う.

• BIT
  verify: AOJ(Range Sum Ouery)
• 二分探索
  verify: yukicoder(かっこいい電車)
  verify: AtCoder(データ構造)
• Two dimensional BIT
  verify: AtCoder(惑星探査)
• Range update Point query BIT
  verify: AOJ(Range Add Query(RAQ))
• Range update Range query BIT
  verify: AOJ(RSQ and RAQ)

int128_t

int128.hpp
128bit整数用のツール

• stream output for int128_t
• convert string to int128_t

Lazy Segment Tree

lazy_segment_tree.hpp
遅延評価セグメントツリー(区間更新, 区間取得) 参考: hatenablog

• LazySegmentTree
  verify: AOJ(Range Update Query)

Mergable Range Set

mergable_range_set.hpp
区間を持ち, 重なりがある場合にマージするデータ構造

• MergableRangeSet
  verify: yukicoder(アメーバがたくさん)

Segment Tree

segment_tree_pu_rq.hpp
セグメントツリー (点更新, 区間取得)

• SegmentTree
  verify: AOJ(Range Minimum Quey)
  verify: AOJ(Range Sum Ouery)

Treap

treap.hpp
平衡二分探索木, Implicit Treapは, 区間取得, k番目の要素をとる, 区間反転などができる

• Treap
  verify: AOJ(Treap)
• Implicit Treap
  verify: yukicoder(平らな農地)

Union Find

union_find.hpp
素集合データ構造 (uniteとfindを高速に行う)

• union find
  verify: AOJ(Disjoint Set: Union Find Tree)
• weighted union find
  verify: AOJ(Weighted Union Find Trees)

Wavelet Matrix

wavelet_matrix.hpp
文字列などの索引

• Wavelet Matrix
  verify: AOJ(Hard Beans)
  verify: yukicoder(平らな農地)
  verify: AOJ(宝探し)
  verify: AOJ(Dungeon(I))

Median

median.hpp
中央値

• Median

Compressed2DSegmentTree

クエリ先読みによる2次元セグメント木のメモリ削減
compressed2d_segment_tree.hpp

• Compressed2DSegmentTree

Sparse Table

(1<<i)ごとに要素の最小値(最大値)を保持しておきクエリにO(1)で返答する
sparse_table_.hpp

• SparseTable
  verify: SPOJ(RMQSQ)
• DisjointSparseTable
  verify: SPOJ(RMQSQ)