Namaran

Code daily. Without assist.

2026-09-28

apply_ranges.cpp

#include <cstddef>
#include <span>
#include <vector>

struct Range {
    std::size_t l, r;
    int v;
};

std::vector<int> apply_ranges(std::size_t n, std::span<const Range> ranges) {
}

長さ n の配列を 0 で初期化し、ranges の各要素 {l, r, v} について添字 l 以上 r 未満の要素すべてに v を足した結果を返す apply_ranges を書いてください。0 <= l <= r <= n とし、手間は区間の長さによらず、n と区間の個数に比例するようにします。ranges が空なら n 個の 0 を返します。apply_ranges(5, {{0, 2, 1}, {1, 5, 3}}) → {1, 4, 3, 3, 3}、apply_ranges(3, {}) → {0, 0, 0}、apply_ranges(0, {}) → {}

Reference
std::vector<int> apply_ranges(std::size_t n, std::span<const Range> ranges) {
    std::vector<int> d(n + 1);
    for (const auto &[l, r, v] : ranges) {
        d[l] += v;
        d[r] -= v;
    }
    std::partial_sum(d.begin(), d.end(), d.begin());
    d.pop_back();
    return d;
}

区間ごとに r - l 個の要素へ足していくと、手間が区間の長さに比例します。そこで差分配列 d を用意し、区間の始まり d[l] に v を足して、終わりの次 d[r] から v を引いておきます。最後に std::partial_sum で先頭から累積すると、各区間の v がちょうど l から r - 1 までに行き渡ります。

d を n 要素ではなく n + 1 要素にしているのは、例の {1, 5, 3} のように r が n に等しい区間でも d[r] に書けるようにするためです。n 要素のままだと範囲外への書き込みになります。累積したあとの最後の要素はどの区間にも属さず、必ず 0 なので、pop_back で捨てれば長さ n の結果になります。

掲載したのは参考実装で、唯一の正解ではありません。r == n のときだけ引かないように分岐すれば、d は n 要素で済みます。