座標圧縮の解説（1次元から2次元の圧縮まで）
座標圧縮は、座標の情報から、位置関係や大小関係だけ抽出するテクニックです。
仮に座標の範囲が非常に広い場合、以下のような不都合が生じてしまいます。
例：\(0\) ~ \(10^9\) の数直線はメモリにのらないダブリングの基本概念とその応用
ダブリングは、全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、「K個先の要素を求めるのに \(O(K)\) かかる」ような状況において
前処理：\(O(N \log K)\) 時間, \(O(N ...ランレングス圧縮と復元
ランレングス圧縮（ランレングス符号化）とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。
同じ文字が連続して何文字出現するかに変換します。
例：
In: aaal ...
区間の和を求めるアルゴリズム（区間の更新なし）
要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 = S + a; }}// - S;}int main() { vector<int>a = {1, 2 ...
二次元での区間和を求めるアルゴリズム（区間の更新なし）
大きさが \(H × W\) の二次元配列 \(a\) 上において、 + a + … + a
+ a + a + … + a
+ …
+ a + a + … + ...
半分全列挙による全探索の高速化
N 個の要素の組み合わせを計算する際、N/2 ずつの2グループに分けてそれぞれを全列挙し、組み合わせ方を高速に求めるという工夫を「半分全列挙」と言います。
選択した数列の合計値を半分全列挙で探索する場合（\(2^4\)ずつに分け ...組み合わせゲーム理論の基礎とGrundy数での勝敗判定アルゴリズム
競技プログラミングなどで頻出のテーマである組み合わせゲームやGrundy数についてまとめました。
前半は全ての方に向けての内容で、プログラム例や競技プログラミング特有の話題については後半にあります。
組み合わせゲーム ...競プロでよく出る区間和問題の解き方まとめ
区間の更新がない場合
クエリ：\(O(1)\)
区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。
一次元の区間和累積和を用いることで、
前処理：\(O(N)\)クエリ：\(O(1)\)
で処理がで ...