2026-09-28
range_add.cpp
#include <array>
#include <numeric>
#include <print>
struct Add {
int l, r, v;
};
int main() {
constexpr Add adds[] = {{0, 3, 1}, {2, 5, 2}, {1, 2, 4}};
std::array<int, 6> d{};
for (auto [l, r, v] : adds) {
d[l] += v;
d[r] -= v;
}
std::partial_sum(d.begin(), d.end(), d.begin());
for (const char *sep = ""; int x : d) {
std::print("{}{}", sep, x);
sep = " ";
}
std::println();
}
これは何を出力するでしょうか?
Answer
1 5 3 2 2 0 です。
ループが終わった時点の d には、足し始める位置に +v、足し終わった次の位置に -v が置かれていて、中身は {1, 4, -2, -1, 0, -2} です。std::partial_sum で先頭から累積すると、d[l] の +v は添字 l から後ろのすべてに効き、d[r] の -v が添字 r から先でそれを打ち消します。そのため各 {l, r, v} は、l 以上 r 未満の半開区間に v を足したことになります。
区間ごとに見ると、{0, 3, 1} は添字 0〜2 に 1、{2, 5, 2} は 2〜4 に 2、{1, 2, 4} は添字 1 だけに 4 を足します。重なりを合計すると 1 5 3 2 2 0 で、r として書いた添字 5 の要素には、どの区間も届きません。
partial_sum は出力先に入力の先頭を渡してよく、d をその場で累積和に置き換えられます。