2026-10-21
prefix_count.rs
fn main() {
let a = [12, 10, 13, 10, 12];
let mut count = [0; 4];
for x in a {
count[x - 10] += 1;
}
for i in 1..count.len() {
count[i] += count[i - 1];
}
println!("{count:?}");
}
これは何を出力するでしょうか?
Answer
[2, 2, 4, 5] です。
値は10から13の範囲にあるので、x - 10 で0から3の添字に移し、長さ4の配列で数えます。最初のループのあと、count は10が2個、11が0個、12が2個、13が1個で [2, 0, 2, 1] です。ここで止めると出現回数がそのまま出ますが、2つ目のループが続きます。
2つ目のループは、添字1から順に、1つ前の要素を自分に足します。前の要素はすでに足し込み済みなので、count[i] は「添字 i 以下の値の個数の合計」になります。count[1] は 0 + 2 = 2、count[2] は 2 + 2 = 4、count[3] は 1 + 4 = 5 です。
この累積の個数は、計数ソートで各値を出力のどこに置くかを表します。たとえば12は、12以下の値が4個あるので、並べ替えた結果の4番目までに収まり、11以下の2個のあと、3番目と4番目に置かれます。