Namaran

Code daily. Without assist.

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 をその場で累積和に置き換えられます。