# 蟻本輪読回 第五回 参考資料(3-3)

## トピック

### ・列の平方分割
### ・遅延評価
### ・Mo's Algorithm

##
## 列の平方分割

列構造に対してクエリが飛んでくるときにいくつかのブロックごとに区切って処理することで計算量を落とすテクニック。
書きやすく、そこそこ速い。

クエリによっては計算量の解析において B + N/B の最小化ではなく、3B + N/B の最小化(下記参照)などになり、この場合は B = sqrt(N/3) とすると定数倍が改善される

#### 例
[StaticRangeSum](https://judge.yosupo.jp/submission/155186 "タイトル")

[PointAddRangeSum](https://judge.yosupo.jp/submission/155187 "タイトル")

[PointAddRangeSum (定数倍改善 B = sqrt(N/3))](https://judge.yosupo.jp/submission/155187 "タイトル")

##
## 遅延評価

データ構造の要素に対して繰り返し写像が与えられるとき(一様加算、chminなど)

愚直に写像ひとつごとに要素を変換していくよりも、あらかじめ合成写像を持っておいて、必要になった時にその合成写像によって変換していく方がよい。

### 遅延評価ただの列

#### 問題例

N人の野球選手が最初にパワーA_iを持っている。
全員がP回の練習を行う。j回目での練習により、パワーはBj倍され、さらにCjが加算される。
全ての練習を終えた後、各選手のパワーはいくつだろうか?
O(N + P)

### 遅延評価平方分割

平方分割でブロックごとに合成写像を持っておくもの。

#### 例
[RangeAffinePointGet](https://judge.yosupo.jp/submission/155217 "タイトル")

### 遅延評価セグメント木

遅延評価平方分割では、端の更新により、ブロック全体が評価されてしまう。その評価の被害を極力減らすには? → 二分木でもつとよい!

#### 例
[RangeAffineRangeSum](https://judge.yosupo.jp/submission/148586 "タイトル")

##
## Mo's Algorithm

列に対する範囲クエリが伸縮操作を高速に行えるものであるとき、クエリの処理の順番をうまく入れ替えることで全体として必要な計算量を落とすことができる。

#### 例
[RangeAffineRangeSum](https://judge.yosupo.jp/submission/126470 "タイトル")

[ABC174F](https://atcoder.jp/contests/abc174/submissions/31781550 "タイトル")