kpfenwick: 競技プログラミング向け Fenwick Tree（BIT）

目的もくてき:

• 点加算・区間和クエリを O(log N) で処理する Fenwick Tree を提供します。

実装じっそう:

• 1-index 内部配列 bit[1..n] を持つ実装です。

注意ちゅうい:

• 公開 API の添字は 0-index、内部では 1-index に変換します。

#entry main
#target std
#import "kp/kpfenwick" as *
#import "std/stdio" as *
fn main <()*> ()> ():
    let f <i32> fenwick_new 5;
    fenwick_add f 0 1;
    fenwick_add f 1 2;
    fenwick_add f 2 3;
    fenwick_add f 3 4;
    print_i32 fenwick_sum_range f 0 3;
    print " ";
    println_i32 fenwick_sum_range f 1 4;
    fenwick_free f

6 9

fenwick_new: 長さ n の Fenwick Tree を作る
fenwick_free: Fenwick Tree の内部領域を解放する
fenwick_add: idx に delta を加算する
fenwick_sum_prefix: 区間 [0, r) の和を返す
fenwick_sum_range: 区間 [l, r) の和を返す