kpprefix: 競技プログラミング向け累積和ユーティリティ

目的もくてき:

• 1 次元累積和の構築と区間和クエリを定型化します。

実装じっそう:

• pref[0]=0, pref[i+1]=pref[i]+a[i] で長さ n+1 の配列を構築します。

注意ちゅうい:

• 値型は i32 です。総和が大きい場合は i64 版へ拡張してください。

#entry main
#target std
#import "kp/kpprefix" as *
#import "core/mem" as *
#import "std/stdio" as *
fn main <()*> ()> ():
    let n <i32> 5;
    let data <i32> alloc_raw mul n 4;
    store_i32 add data 0 1;
    store_i32 add data 4 2;
    store_i32 add data 8 3;
    store_i32 add data 12 4;
    store_i32 add data 16 5;
    let pref <i32> prefix_build_i32 data n;
    print_i32 prefix_range_sum_i32 pref 0 3;
    print " ";
    println_i32 prefix_range_sum_i32 pref 1 5;
    dealloc_raw pref mul add n 1 4;
    dealloc_raw data mul n 4

6 14

prefix_build_i32: data[0..n) の累積和配列 pref[0..n] を作る
prefix_range_sum_i32: 半開区間 [l, r) の和を返す
PrefixI32: i32 用累積和の安全ハンドル

目的もくてき:

• 累積和配列ポインタと長さをまとめ、生ポインタの露出を減らします。

注意ちゅうい:

• pointer と長さだけを持もつ軽量けいりょう handle なので Copy / Clone を実装じっそうします。

prefix_build_vec_i32: Vec<i32> から累積和ハンドルを作る

実装じっそう:

• vec_data_len で data pointer と長さを 1 回で取とり出だしてから、raw prefix builder へ委譲いじょうします。

prefix_sum_i32: ハンドルから半開区間 [l,r) の和を返す
prefix_free_i32: 累積和ハンドルのメモリを解放する