累積和

言わずと知れたやつ。
区間和をクエリ毎に \({\rm O}(1)\) で求める。
累積「和」と言っているが、逆演算（加算に対する減算のようなもの）が存在すれば和でなくてもよい（ bitwise xor など）。
累積積もこれでできるが、入力に 0 がない場合に限られる（ 0 がある場合はセグ木
だと思ってたけど、区間内に含まれる 0 の個数は累積和で求まるので
「区間内に 0 が 1 個以上あったら答えは 0、そうじゃなかったら累積積同士の割り算」でできる）。
数え上げで \(f(B)-f(A-1)\) みたいにするやつも累積和の一種。

エックスオア多橋君は木に対して累積和を使っているイメージ。

mod数列

いもす法

「最後に累積和をとれば求めたい数列になる」ようにすることで、区間に対する書き換えがクエリ毎に \({\rm O}(1)\) でできる。

セグ木

逆演算が存在しなくても使えるやつ。
RMQ などはこれ。
区間に対する演算と、1 つの頂点に対する書き換えがそれぞれ \({\rm O}(\log N)\) でできる。
書き換えは葉に対して行うことが多いが、そうでない頂点に対しても行える。

BIT

セグ木と似ているが、逆演算ができなくてもいい場合にのみ使える。
区間に対する演算と、1 つの頂点に対する書き換えがそれぞれ \({\rm O}(\log N)\) でできる。
セグ木よりも表現力が低いが、コード量が少なくて済むので（人によっては）実装が楽だったり、コードゴルフに役立ったりする。
転倒数の問題では解説で BIT を使うように書かれていることが多いが当然セグ木でもできる。

平方分割

平方根分割のほうが適切だと思うが平方分割と呼ばれている。
セグ木と表現力は同じだが計算量が大きい。
区間に対する演算と、1 つの頂点に対する書き換えがそれぞれ \({\rm O}(\sqrt N)\) でできる。
実装が楽。
遅延セグ木の代用品になるらしい。

遅延セグ木

普通のセグ木よりも表現力が高い。
区間に対する演算と、区間に対する一様な書き換えがそれぞれ \({\rm O}(\log N)\) でできる。
いもす法で解ける問題は（ TLE しなければ）遅延セグ木でも解ける。
実装がつらい。

Splarraay ｽﾌﾟﾗﾚｪｰｲ
クエリ全部盛り（まだ解いてない）

尺取り法

区間の右端を伸ばしたり左端を縮めたりする \({\rm O}(N)\) のやつ。
逆演算が存在する場合に使える。
伸ばせるだけ伸ばすやつと、区間の幅が固定のやつがある。

スライド最小値

固定幅の区間に対する RMQ が \({\rm O}(N)\) でできる（ deque を使う）。
尺取りっぽい感じがある。
RMQ の一種なので（ TLE しなければ）セグ木でもできる。
（ TLE しなければ）値とインデックスのペアを使う優先度付きキューでもできる（優先度付きキューでできることは multiset でもできる）。

Mo's algorithm

単に Mo と言う場合もある。
書き換えが起こらなくて逆演算が存在するものに対して、
クエリを先読みして、「区間の左端と右端をそれぞれ \(\sqrt N\) で割った商のペア」についてソートしておいて、
\({\rm O}((N+Q)\sqrt N)\) で尺取りっぽくやる。
区間を伸ばすのを縮めるのよりも先にやらないとおかしくなる場合がある。
累積和と一緒に使うこともある。

ニワンゴくんの約数

Sparse Table

使ったことがないので詳しくは分からないが、そういうものがあるらしい。
書き換えが起こらない場合に RMQ がクエリ毎に \({\rm O}(1)\) でできるらしい。

37.50.48

%20 のブログ

区間に関するやつ

累積和