1. 累積和のテク
- （実装段階で range sum をするための道具ではなく）考察段階で累積和が出てくるタイプのテクニック
- クエリ先読みでほしい prefix sum を取得して、平面走査をする
- $A_l + \ldots A_{r-1} = S_r - S_l$ と考え、$S_r$ と $S_l$ をバラバラに扱って考察をするとうまくいく
- だんだん累積和を作り上げる（オンラインアルゴリズム）
- 最初に前処理としてまとめて作るのではなく、だんだん作っていく
- 問題例
2. 逆元が存在しないモノイドでの累積
- 1次元で1点抜けまたは区間抜けの総積を求めたい場合
- 2次元で1点抜けまたは矩形抜けの総積を求めたい場合
メモ
3. 多次元累積和
$D$ 次元配列 $a$ に対して、累積和 $P$ を
$$
P(r)=\sum_{x\in\prod_{i\in[D]}[0,r_i)}a(x)
$$
と定義する。
$S\subseteq[D]$ に対して、$u^{(S)}$ を
$$
u_i^{(S)}=
\begin{cases}
l_i & (i\in S)\\
r_i & (i\notin S)
\end{cases}
$$
と定義する。
このとき、直方体領域 $\displaystyle\prod_{i\in[D]}[l_i,r_i)$ での $a$ の和は
$$
\sum_{x\in\prod_{i\in[D]}[l_i,r_i)}a(x)
\sum_{S\subseteq[D]}
(-1)^{|S|}P(u^{(S)})
$$
で求められる。