2026-10-20
range_add.cpp
struct Blocks {
int b;
std::vector<int> a, tag;
int get(int i) const { return a[i] + tag[i / b]; }
};
void add(Blocks& s, int l, int r, int x) {
}
配列を b 要素ずつの塊に分けて持つ Blocks の、区間 [l, r) のすべての要素に x を足す add を書いてください。要素 i の値は、get のとおり a[i] とその要素を含む塊の tag の和です。区間に丸ごと入る塊はその塊の tag に足し、一部だけが入る塊は区間に入る要素の a に1つずつ足します。l == r のときは何も変えません。例の s は、b が3で、8個の a と3個の tag がすべて0の状態から add を1回呼んだもので、出力例は s.get(0) から s.get(7) までを並べたものです。
入力例 1
add(s, 1, 7, 5)
出力例 1
0 5 5 5 5 5 5 0
入力例 2
add(s, 4, 4, 9)
出力例 2
0 0 0 0 0 0 0 0
入力例 3
add(s, 0, 8, 2)
出力例 3
2 2 2 2 2 2 2 2
Reference
void add(Blocks& s, int l, int r, int x) {
for (; l < r && l % s.b != 0; ++l) s.a[l] += x;
for (; l + s.b <= r; l += s.b) s.tag[l / s.b] += x;
for (; l < r; ++l) s.a[l] += x;
}
左端 l が塊の境目に来るまでは a に1つずつ足し、境目からは塊を丸ごと覆えるあいだ tag に足し、最後に残った要素をまた a に足します。入力例 1 では a[1] と a[2] に足したあと tag[1] に足し、残った a[6] に足します。丸ごと入る塊の中は1つずつ書き換えないので、1回の add で触る値の数は、両端の要素が合わせて塊の大きさの2倍未満、tag が塊の数以下に収まります。
3つのループの条件は l < r か l + s.b <= r を含むので、l == r ならどれも1回も回りません。入力例 3 の最後の塊は要素6、7、8にあたりますが、配列は要素7で終わるので 6 + 3 <= 8 が成り立たず、tag[2] ではなく a[6] と a[7] に足されます。
掲載したのは参考実装で、唯一の正解ではありません。要素ごとに、その要素を含む塊が区間に丸ごと入るかを調べて足し先を選ぶ書き方もあります。