2026-10-20
block_sum.cpp
#include <iostream>
#include <vector>
int main() {
const std::vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6, 5};
const int b = 3;
std::vector<int> block(3);
for (int i = 0; i < 9; ++i) block[i / b] += a[i];
int l = 2, r = 9, sum = 0, steps = 0;
for (; l < r && l % b != 0; ++l, ++steps) sum += a[l];
for (; l + b <= r; l += b, ++steps) sum += block[l / b];
for (; l < r; ++l, ++steps) sum += a[l];
std::cout << sum << ' ' << steps << '\n';
}
これは何を出力するでしょうか?
Answer
32 3 です。
block[k] には、a[3k] から a[3k + 2] までの3要素の和が入っています。区間 [l, r) の和は3つのループで求めます。l が塊の境目に来るまで1要素ずつ足し、塊を丸ごと足せるあいだは block を足し、最後に残った要素をまた1つずつ足します。steps は、どのループでも足し算を1回するたびに1増えます。
l = 2 は境目ではないので、最初のループで a[2] の4を足し、l は3になります。3は境目なので、2つ目のループに移ります。3 + 3 <= 9 で block[1] の15(1 + 5 + 9)を、6 + 3 <= 9 で block[2] の13(2 + 6 + 5)を足すと、l は9になって3つ目のループは回りません。和は 4 + 15 + 13 = 32、足し算は3回です。
7個の要素の和が3回の足し算で求まりました。長さ n の配列を √n 個程度ずつの塊に分けておくと、端で1つずつ足す要素も、丸ごと足す塊も、それぞれ √n 個程度で済みます。この方法を平方分割(sqrt decomposition)といいます。