古典データ構造 Fenwick Tree（Binary Indexed Tree, BIT） を Zig の CLI として書いた。累積和と一点更新をどちらも
O(log n)・メモリn語でこなし、さらに二分昇降でO(log n)の 順位検索（find-by-rank / select） まで持つ。構造の肝はたった 1 つのビット技:i & -i（最下位ビット）。ポートフォリオで初の Zig 案件で、依存ゼロ・単一の静的バイナリ。これまでの Rust/Go に言語の幅を足す一手。
📦 GitHub: https://github.com/sen-ltd/fenwick-tree-cli
なぜ Zig か
直近はアルゴリズム CLI を Rust/Go で交互に出してきたが、言語の幅を見せるために Zig 0.16 を採用した。Zig は「隠れた制御フロー・隠れたメモリ確保が無い」低レベル系言語で、i & -i のようなビット操作や、明示的アロケータでの配列管理と相性が良い。しかもクロスコンパイルが標準機能なので、-Dtarget=x86_64-linux-musl 一発で静的 Linux バイナリが出る（Docker 不要）。
配列は stdin から、操作は引数として左から順に適用する（更新は後続クエリに反映される）:
$ echo "120 80 200 150 90 300 250 60 180 140 220 100" | \
fen p:3 r:4:6 k:600 u:2:500 p:3 k:600 sum
built Fenwick tree: n=12, total=1890
prefix[1..3] = 400 # 1〜3月の累積売上
range[4..6] = 540 # 窓の合計, O(log n)
find rank 600 = index 5 # 累積が初めて 600 に届くのは 5月
update idx 2 += 500 (total now 2390)
prefix[1..3] = 900 # 一点更新が即反映
find rank 600 = index 2 # …なので 600 到達は 2月に前倒し
sum = 2390
たった 1 つのアイデア: i & -i
1-based の添字 i は、配列のうち 最下位ビット i & -i の長さの区間を担当する。6 (0b110) は 2 要素、8 (0b1000) は 8 要素、12 (0b1100) は 4 要素。この 1 事実がすべてを生む:
pub fn lowbit(i: usize) usize {
return i & (~i +% 1); // i & -i（符号なしなのでラップ付き否定）
}
累積和 は最下位ビットを剥がしながら 0 に向かって区間を飛ぶ:
pub fn prefix(self: *const Fenwick, i: usize) i64 {
var s: i64 = 0;
var x = i;
while (x > 0) : (x -= lowbit(x)) s += self.tree[x];
return s;
}
一点更新 は逆に足しながら n に向かって登る:
pub fn update(self: *Fenwick, i: usize, delta: i64) void {
var x = i;
while (x <= self.n) : (x += lowbit(x)) self.tree[x] += delta;
}
どちらの歩みもセットビット 1 個につき 1 ノードを触るだけ ——O(log n)。range(l, r) は prefix(r) - prefix(l-1) で済み、fromSlice は各スロットの部分和を親へ押し上げることで n 回の update ではなく O(n) で木を組む。
おまけ: 二分昇降で順位検索を 1 回の降下で
格納値が非負（頻度表）なら、同じ木で 「累積が K に初めて届く最小の添字は?」——順位検索 / select——を、別の構造なしに二分昇降（2 の冪を大きい順に試す）で O(log n) 1 回の降下で答えられる:
pub fn findByRank(self: *const Fenwick, k: i64) usize {
var pos: usize = 0;
var rem = k;
var pw = floorPow2(self.n);
while (pw > 0) : (pw >>= 1) {
const next = pos + pw;
if (next <= self.n and self.tree[next] < rem) {
pos = next;
rem -= self.tree[pos];
}
}
return pos + 1;
}
ランダム化テストが、200 回の更新を挟んだ後の findByRank を線形走査の参照と突き合わせて確認する（findByRank after updates stays consistent with a linear scan）。
Zig 0.16 の作法メモ
0.16 は I/O が刷新（Writergate）されており、main は pub fn main(init: std.process.Init) !void を取り、init.gpa（アロケータ）・init.io・init.minimal.args（引数）が渡ってくる。標準出力は std.Io.File.stdout().writeStreamingAll(io, bytes)、標準入力は std.posix.read(STDIN_FILENO, ...)。std.ArrayList はアンマネージド化し、.empty 初期化＋各メソッドにアロケータを渡す形になった。
src/fenwick.zig — 木: lowbit, prefix, update, range, findByRank（テスト 7 件）
src/main.zig — CLI: 配列は stdin, 操作 (p/r/u/k/sum) は引数
まとめ
Fenwick Tree は「累積和と一点更新を両方 O(log n)」の定番で、実装は i & -i の一点突破。順位検索まで同じ木で二分昇降で解けるのが美しい。言語は Zig を選び、Rust/Go に続く 3 つ目の系統として、ビット操作と明示的メモリ・クロスコンパイルという Zig の持ち味を載せた。