n updates.
The bonus: find-by-rank in one descent
When the stored values are non-negative (a frequency table), the same tree
answers "what is the smallest index whose running total reaches K?" — a select
/ find-by-rank — in a single O(log n) descent by binary lifting over powers of
two, with no separate structure:
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;
}
A randomized test cross-checks it against a linear scan after 200 interleaved
updates.
Zig 0.16 notes
0.16 reworked I/O (the "Writergate" changes). main takes
pub fn main(init: std.process.Init) !void, handing you init.gpa (an
allocator), init.io, and init.minimal.args. Stdout is
std.Io.File.stdout().writeStreamingAll(io, bytes); stdin is
std.posix.read(STDIN_FILENO, ...). std.ArrayList is now unmanaged — you
.empty-initialize and pass the allocator to each method.
src/fenwick.zig — the tree: lowbit, prefix, update, range, findByRank (7 tests)
src/main.zig — CLI: array on stdin, ops (p/r/u/k/sum) as arguments
Takeaway
A Fenwick tree gives you O(log n) prefix sums and point updates from one bit
trick, i & -i, and the same tree does select by binary lifting. I built it in
Zig to add a third language lineage next to the recent Rust and Go, leaning on
Zig's strengths: bit-level work, explicit memory, and effortless
cross-compilation.
📦 GitHub: https://github.com/sen-ltd/fenwick-tree-cli