二次元累積和 - kamojirobrothersのブログ

ABC106のD問題の解説の二重累積和がよくわからなかったので、簡単に証明をつけた。
まず、 ${A = (a_{ij})}$ を二重配列と考えます。
${A}$ の各列の累積和を取ったものを ${B = (b_{ij})}$ とします。
すると、
${b_{ij} = \sum_{k=1}^i a_{ij}}$
となります。
次に、 ${B}$ の各行の累積和を取ったものを ${C = (c_{ij})}$ とします。
すると、
${c_{ij} = \sum_{l=1}^j b_{il} = \sum_{l=1}^j \sum_{k=1}^i a_{kl}}$
となります。
というわけで、 ${C}$ の各成分が ${A}$ の ${i\times j}$ の長方形に囲まれた部分の成分の和になります。
納得。