2026-10-20
point_set.cpp
#include <iostream>
int a[] = {1, 2, 3, 4};
int block[] = {3, 7}; // block[k] = a[2k] + a[2k + 1]
void set(int i, int x) {
a[i] = x;
block[i / 2] += x - a[i];
}
int prefix(int r) { // a[0] + ... + a[r - 1]
int s = 0, i = 0;
for (; i + 2 <= r; i += 2) s += block[i / 2];
for (; i < r; ++i) s += a[i];
return s;
}
int main() {
set(1, 10);
std::cout << prefix(1) << ' ' << prefix(2) << ' ' << prefix(3) << '\n';
}
a を2要素ずつの塊に分け、塊ごとの和を block に持つことで、先頭から r 個の和 prefix(r) を少ない足し算で求めるコードです。main は set(1, 10) で a[1] を10に変えてから、prefix(1)、prefix(2)、prefix(3) を表示します。いまの出力は 1 3 6 で、本来の出力は 1 11 14 です。
Answer
Wrong
a[i] = x;
block[i / 2] += x - a[i];
2行目は、要素が変わった分 x - a[i] を塊の和に足して、block を a と合わせるつもりの行です。しかし1行目で a[i] はすでに x に書き換わっているので、x - a[i] は常に0になり、block[0] は古い和の3のまま残ります。
prefix(1) は塊を使わず a[0] だけを足すので、正しく1になります。prefix(2) は block[0] の3をそのまま返し、prefix(3) はそれに a[2] の3を足して6です。1要素ずつ足す部分は新しい a を、塊で足す部分は古い block を読むので、区間によって正しい答えと間違った答えが混ざります。
Right
block[i / 2] += x - a[i];
a[i] = x;
古い a[1] の2が残っているうちに差分 10 - 2 = 8 を block[0] に足し、そのあとで a[1] を書き換えます。block[0] は11になり、prefix(2) は11、prefix(3) は 11 + 3 = 14 です。差分を使う更新では、古い値を読み終えるまで上書きしないことが、2つの配列を食い違わせない条件になります。