以下の内容はhttps://blog.hamayanhamayan.com/entry/2017/04/12/180257より取得しました。
平方分割
- Square Root Decomposition
- 区間に対するクエリに対して高速に処理できる
- ここが詳しい
- 区間でのクエリであるが、ソートして平方分割して、各バケットでクエリに入る要素だけ抜き出す平方分割もある
- こういう問題
- 1.添字と共に昇順ソート 2.バケット毎に添え字ソート 3.各クエリについて全てのバケットのans[L][R]を取得してマージ
- 出現頻度を扱う場合は平方分割が多いイメージ
- クエリの平方分割
- 取得クエリだけで更新クエリが無い場合はバケットの間の処理は事前計算することで、処理をより軽くすることができる場合がある この解説
問題
- 平方分割
- クエリの範囲で分けない平方分割
- クエリの平方分割
- 二次元平方分割
以上の内容はhttps://blog.hamayanhamayan.com/entry/2017/04/12/180257より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14
