DEV Community

SEN LLC
SEN LLC

Posted on

Building a Fenwick Tree (BIT) CLI in Zig — It All Hangs on i & -i: O(log n) Prefix Sums, Point Updates, and Binary-Lifted Select

#zig #algorithms #datastructures #cli

The classic Fenwick tree (Binary Indexed Tree) as a Zig CLI. Prefix sums and point updates both in O(log n) and n words of memory, plus an O(log n) find-by-rank (select) via binary lifting — all hanging on one bit trick, i & -i, the lowest set bit. My first Zig entry, adding a language beyond the recent Rust/Go run; no dependencies, a single static binary.

📦 GitHub: https://github.com/sen-ltd/fenwick-tree-cli

Screenshot

Why Zig

The recent algorithm CLIs alternated Rust and Go; to show some language breadth I
reached for Zig 0.16. Zig is a low-level language with no hidden control flow
and no hidden allocation, which suits bit tricks like i & -i and explicit,
allocator-driven arrays. And cross-compilation is built in, so a static Linux
binary is one flag away — no Docker required.

The array comes from stdin; operations are arguments applied left to right, so
updates are visible to later queries:

$ 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            # cumulative sales, months 1..3
  range[4..6]    = 540            # sum of a window, O(log n)
  find rank 600    = index 5      # cumulative first reaches 600 at month 5
  update idx 2 += 500  (total now 2390)
  prefix[1..3]   = 900            # the point update is live
  find rank 600    = index 2      # ...so now 600 is reached by month 2
  sum            = 2390
Enter fullscreen mode Exit fullscreen mode

The one idea: i & -i

Index i (1-based) is made responsible for a slice of the array whose length is
its lowest set bit, i & -i. Index 6 (0b110) covers 2 elements, index 8
(0b1000) covers 8, index 12 (0b1100) covers 4. That single fact gives you
everything:

pub fn lowbit(i: usize) usize {
    return i & (~i +% 1); // i & -i, with wrapping negation on unsigned
}
Enter fullscreen mode Exit fullscreen mode

Prefix sum peels the lowest set bit off, jumping across those slices toward 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;
}
Enter fullscreen mode Exit fullscreen mode

Point update adds it back, walking toward 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;
}
Enter fullscreen mode Exit fullscreen mode

Each walk touches one node per set bit — O(log n). range(l, r) is just
prefix(r) - prefix(l-1), and fromSlice builds the whole tree in O(n) by
pushing each slot's partial sum to its parent instead of doing 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;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)