累積和のテク

• （実装段階で range sum をするための道具ではなく）考察段階で累積和が出てくるタイプのテクニック
  • クエリ先読みでほしい prefix sum を取得して、平面走査をする
    • ABC248 D - Range Count Query
    • Library Checker - Rectangle Sum
  • $A_l + \ldots A_{r-1} = S_r - S_l$ と考え、$S_r$ と $S_l$ をバラバラに扱って考察をするとうまくいく
    • ABC370 E - Avoid K Partition
• だんだん累積和を作り上げる（オンラインアルゴリズム）
  • 最初に前処理としてまとめて作るのではなく、だんだん作っていく
  • 問題例
    • ABC389 C - Snake Queue
    • ABC388 D - Coming of Age Celebration（いもす法）

多次元累積和

包除原理

逆元が存在しないモノイドでの累積

• 1次元で1点抜けまたは区間抜けの総積を求めたい場合
  • 左から累積と右から累積を考える
• 2次元で1点抜けまたは矩形抜けの総積を求めたい場合
  • 左上、右上、右下、左下からの累積を考える (ゼータ変換のノリで累積を求める)
  • 例: ABC347 F - Non-overlapping Squares

メモ

• セグ木との組合せ
  • Range Add Query (RAQ)を図でわかりやすく解説 #C++ - Qiita

ゼータ変換