966 Advanced

966 Fenwick Tree

Functional Programming

Tutorial

The Problem

Implement a Fenwick tree (Binary Indexed Tree) for O(log n) prefix sum queries and point updates. The key operation is lowbit(i) = i & (-i) — isolating the lowest set bit — which drives both update traversal (add lowbit to climb) and query traversal (subtract lowbit to descend). The tree is 1-indexed internally for clean bit arithmetic.

🎯 Learning Outcomes

• Implement update(i, delta): starting at 1-indexed position i+1, add delta to tree[idx] and advance via idx += lowbit(idx)

• Implement prefix_sum(i): starting at i+1, accumulate tree[idx] and retreat via idx -= lowbit(idx)

• Implement range_sum(l, r) as prefix_sum(r) - prefix_sum(l-1)

• Understand why i & (-i) in two's complement isolates the lowest set bit

• Build a Fenwick tree from an array in O(n) using incremental updates

Code Example

#![allow(clippy::all)]
// 966: Fenwick Tree (Binary Indexed Tree)
// O(log n) point update and prefix sum
// Key trick: lowbit(i) = i & (-i) traverses the tree

pub struct FenwickTree {
    n: usize,
    tree: Vec<i64>, // 1-indexed internally
}

impl FenwickTree {
    pub fn new(n: usize) -> Self {
        FenwickTree {
            n,
            tree: vec![0i64; n + 1],
        }
    }

    pub fn from_slice(arr: &[i64]) -> Self {
        let mut fw = FenwickTree::new(arr.len());
        for (i, &v) in arr.iter().enumerate() {
            fw.update(i, v);
        }
        fw
    }

    /// Point update: add `delta` to position `i` (0-indexed)
    pub fn update(&mut self, i: usize, delta: i64) {
        let mut idx = (i + 1) as i64; // convert to 1-indexed
        while idx <= self.n as i64 {
            self.tree[idx as usize] += delta;
            idx += idx & (-idx); // idx += lowbit(idx)
        }
    }

    /// Set position `i` to `value` (requires knowing current value)
    pub fn set(&mut self, i: usize, value: i64) {
        let current = self.range_sum(i, i);
        self.update(i, value - current);
    }

    /// Prefix sum [0, i] inclusive (0-indexed)
    pub fn prefix_sum(&self, i: usize) -> i64 {
        let mut idx = (i + 1) as i64; // convert to 1-indexed
        let mut sum = 0i64;
        while idx > 0 {
            sum += self.tree[idx as usize];
            idx -= idx & (-idx); // idx -= lowbit(idx)
        }
        sum
    }

    /// Range sum [l, r] inclusive (0-indexed)
    pub fn range_sum(&self, l: usize, r: usize) -> i64 {
        if l == 0 {
            self.prefix_sum(r)
        } else {
            self.prefix_sum(r) - self.prefix_sum(l - 1)
        }
    }

    pub fn len(&self) -> usize {
        self.n
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn make_fw() -> FenwickTree {
        FenwickTree::from_slice(&[1, 3, 5, 7, 9, 11])
    }

    #[test]
    fn test_prefix_sums() {
        let fw = make_fw();
        assert_eq!(fw.prefix_sum(0), 1);
        assert_eq!(fw.prefix_sum(2), 9); // 1+3+5
        assert_eq!(fw.prefix_sum(5), 36); // total
    }

    #[test]
    fn test_range_sums() {
        let fw = make_fw();
        assert_eq!(fw.range_sum(0, 2), 9); // 1+3+5
        assert_eq!(fw.range_sum(2, 4), 21); // 5+7+9
        assert_eq!(fw.range_sum(1, 3), 15); // 3+5+7
        assert_eq!(fw.range_sum(5, 5), 11); // single element
    }

    #[test]
    fn test_update() {
        let mut fw = make_fw();
        fw.update(2, 5); // arr[2] += 5 → 10
        assert_eq!(fw.prefix_sum(5), 41);
        assert_eq!(fw.range_sum(0, 2), 14);
        assert_eq!(fw.range_sum(2, 4), 26);
    }

    #[test]
    fn test_single_element() {
        let mut fw = FenwickTree::new(1);
        fw.update(0, 42);
        assert_eq!(fw.prefix_sum(0), 42);
        assert_eq!(fw.range_sum(0, 0), 42);
    }

    #[test]
    fn test_set() {
        let mut fw = make_fw();
        fw.set(2, 10); // set arr[2] = 10 (was 5)
        assert_eq!(fw.range_sum(2, 2), 10);
        assert_eq!(fw.prefix_sum(5), 41);
    }
}

(* 966: Fenwick Tree (Binary Indexed Tree) *)
(* Point update + prefix sum in O(log n). Uses 1-based indexing internally. *)

type fenwick = {
  n: int;
  tree: int array;  (* 1-indexed *)
}

let create n = { n; tree = Array.make (n + 1) 0 }

(* lowbit: lowest set bit of i *)
let lowbit i = i land (-i)

(* Point update: add delta to position i (1-indexed externally) *)
let update fw i delta =
  let i = ref (i + 1) in  (* convert to 1-indexed *)
  while !i <= fw.n do
    fw.tree.(!i) <- fw.tree.(!i) + delta;
    i := !i + lowbit !i
  done

(* Prefix sum [0, i] inclusive (0-indexed externally) *)
let prefix_sum fw i =
  let i = ref (i + 1) in  (* convert to 1-indexed *)
  let s = ref 0 in
  while !i > 0 do
    s := !s + fw.tree.(!i);
    i := !i - lowbit !i
  done;
  !s

(* Range sum [l, r] inclusive (0-indexed) *)
let range_sum fw l r =
  if l = 0 then prefix_sum fw r
  else prefix_sum fw r - prefix_sum fw (l - 1)

(* Build from array *)
let build arr =
  let n = Array.length arr in
  let fw = create n in
  Array.iteri (fun i v -> update fw i v) arr;
  fw

let () =
  let arr = [| 1; 3; 5; 7; 9; 11 |] in
  let fw = build arr in

  assert (prefix_sum fw 0 = 1);
  assert (prefix_sum fw 2 = 9);   (* 1+3+5 *)
  assert (prefix_sum fw 5 = 36);  (* total *)

  assert (range_sum fw 0 2 = 9);
  assert (range_sum fw 2 4 = 21);
  assert (range_sum fw 1 3 = 15);

  (* Update arr[2] += 5: now arr[2] = 10 instead of 5 *)
  update fw 2 5;
  assert (prefix_sum fw 5 = 41);
  assert (range_sum fw 0 2 = 14);
  assert (range_sum fw 2 4 = 26);

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Lowbit	`idx & (-idx)`	`idx land (- idx)`
Index conversion	`(i + 1) as i64` then cast back	Same arithmetic
Signed arithmetic	`i64` for safe negation	`int` (63-bit on 64-bit systems)
`range_sum`	`prefix(r) - prefix(l-1)`	Same

The Fenwick tree uses O(n) space and O(log n) time for both operations, making it more cache-friendly and simpler to implement than a segment tree — at the cost of supporting only prefix-sum-decomposable queries (no arbitrary range functions like min/max).

OCaml Approach

type t = {
  n: int;
  tree: int array;  (* 1-indexed *)
}

let create n = { n; tree = Array.make (n + 1) 0 }

let lowbit i = i land (-i)

let update fw i delta =
  let idx = ref (i + 1) in
  while !idx <= fw.n do
    fw.tree.(!idx) <- fw.tree.(!idx) + delta;
    idx := !idx + lowbit !idx
  done

let prefix_sum fw i =
  let idx = ref (i + 1) in
  let sum = ref 0 in
  while !idx > 0 do
    sum := !sum + fw.tree.(!idx);
    idx := !idx - lowbit !idx
  done;
  !sum

OCaml's land and unary - correspond to Rust's & and unary -. Both implementations use the same while loop structure with ref (OCaml) vs let mut (Rust) for mutable indices.

Full Source

#![allow(clippy::all)]
// 966: Fenwick Tree (Binary Indexed Tree)
// O(log n) point update and prefix sum
// Key trick: lowbit(i) = i & (-i) traverses the tree

pub struct FenwickTree {
    n: usize,
    tree: Vec<i64>, // 1-indexed internally
}

impl FenwickTree {
    pub fn new(n: usize) -> Self {
        FenwickTree {
            n,
            tree: vec![0i64; n + 1],
        }
    }

    pub fn from_slice(arr: &[i64]) -> Self {
        let mut fw = FenwickTree::new(arr.len());
        for (i, &v) in arr.iter().enumerate() {
            fw.update(i, v);
        }
        fw
    }

    /// Point update: add `delta` to position `i` (0-indexed)
    pub fn update(&mut self, i: usize, delta: i64) {
        let mut idx = (i + 1) as i64; // convert to 1-indexed
        while idx <= self.n as i64 {
            self.tree[idx as usize] += delta;
            idx += idx & (-idx); // idx += lowbit(idx)
        }
    }

    /// Set position `i` to `value` (requires knowing current value)
    pub fn set(&mut self, i: usize, value: i64) {
        let current = self.range_sum(i, i);
        self.update(i, value - current);
    }

    /// Prefix sum [0, i] inclusive (0-indexed)
    pub fn prefix_sum(&self, i: usize) -> i64 {
        let mut idx = (i + 1) as i64; // convert to 1-indexed
        let mut sum = 0i64;
        while idx > 0 {
            sum += self.tree[idx as usize];
            idx -= idx & (-idx); // idx -= lowbit(idx)
        }
        sum
    }

    /// Range sum [l, r] inclusive (0-indexed)
    pub fn range_sum(&self, l: usize, r: usize) -> i64 {
        if l == 0 {
            self.prefix_sum(r)
        } else {
            self.prefix_sum(r) - self.prefix_sum(l - 1)
        }
    }

    pub fn len(&self) -> usize {
        self.n
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn make_fw() -> FenwickTree {
        FenwickTree::from_slice(&[1, 3, 5, 7, 9, 11])
    }

    #[test]
    fn test_prefix_sums() {
        let fw = make_fw();
        assert_eq!(fw.prefix_sum(0), 1);
        assert_eq!(fw.prefix_sum(2), 9); // 1+3+5
        assert_eq!(fw.prefix_sum(5), 36); // total
    }

    #[test]
    fn test_range_sums() {
        let fw = make_fw();
        assert_eq!(fw.range_sum(0, 2), 9); // 1+3+5
        assert_eq!(fw.range_sum(2, 4), 21); // 5+7+9
        assert_eq!(fw.range_sum(1, 3), 15); // 3+5+7
        assert_eq!(fw.range_sum(5, 5), 11); // single element
    }

    #[test]
    fn test_update() {
        let mut fw = make_fw();
        fw.update(2, 5); // arr[2] += 5 → 10
        assert_eq!(fw.prefix_sum(5), 41);
        assert_eq!(fw.range_sum(0, 2), 14);
        assert_eq!(fw.range_sum(2, 4), 26);
    }

    #[test]
    fn test_single_element() {
        let mut fw = FenwickTree::new(1);
        fw.update(0, 42);
        assert_eq!(fw.prefix_sum(0), 42);
        assert_eq!(fw.range_sum(0, 0), 42);
    }

    #[test]
    fn test_set() {
        let mut fw = make_fw();
        fw.set(2, 10); // set arr[2] = 10 (was 5)
        assert_eq!(fw.range_sum(2, 2), 10);
        assert_eq!(fw.prefix_sum(5), 41);
    }
}

(* 966: Fenwick Tree (Binary Indexed Tree) *)
(* Point update + prefix sum in O(log n). Uses 1-based indexing internally. *)

type fenwick = {
  n: int;
  tree: int array;  (* 1-indexed *)
}

let create n = { n; tree = Array.make (n + 1) 0 }

(* lowbit: lowest set bit of i *)
let lowbit i = i land (-i)

(* Point update: add delta to position i (1-indexed externally) *)
let update fw i delta =
  let i = ref (i + 1) in  (* convert to 1-indexed *)
  while !i <= fw.n do
    fw.tree.(!i) <- fw.tree.(!i) + delta;
    i := !i + lowbit !i
  done

(* Prefix sum [0, i] inclusive (0-indexed externally) *)
let prefix_sum fw i =
  let i = ref (i + 1) in  (* convert to 1-indexed *)
  let s = ref 0 in
  while !i > 0 do
    s := !s + fw.tree.(!i);
    i := !i - lowbit !i
  done;
  !s

(* Range sum [l, r] inclusive (0-indexed) *)
let range_sum fw l r =
  if l = 0 then prefix_sum fw r
  else prefix_sum fw r - prefix_sum fw (l - 1)

(* Build from array *)
let build arr =
  let n = Array.length arr in
  let fw = create n in
  Array.iteri (fun i v -> update fw i v) arr;
  fw

let () =
  let arr = [| 1; 3; 5; 7; 9; 11 |] in
  let fw = build arr in

  assert (prefix_sum fw 0 = 1);
  assert (prefix_sum fw 2 = 9);   (* 1+3+5 *)
  assert (prefix_sum fw 5 = 36);  (* total *)

  assert (range_sum fw 0 2 = 9);
  assert (range_sum fw 2 4 = 21);
  assert (range_sum fw 1 3 = 15);

  (* Update arr[2] += 5: now arr[2] = 10 instead of 5 *)
  update fw 2 5;
  assert (prefix_sum fw 5 = 41);
  assert (range_sum fw 0 2 = 14);
  assert (range_sum fw 2 4 = 26);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    fn make_fw() -> FenwickTree {
        FenwickTree::from_slice(&[1, 3, 5, 7, 9, 11])
    }

    #[test]
    fn test_prefix_sums() {
        let fw = make_fw();
        assert_eq!(fw.prefix_sum(0), 1);
        assert_eq!(fw.prefix_sum(2), 9); // 1+3+5
        assert_eq!(fw.prefix_sum(5), 36); // total
    }

    #[test]
    fn test_range_sums() {
        let fw = make_fw();
        assert_eq!(fw.range_sum(0, 2), 9); // 1+3+5
        assert_eq!(fw.range_sum(2, 4), 21); // 5+7+9
        assert_eq!(fw.range_sum(1, 3), 15); // 3+5+7
        assert_eq!(fw.range_sum(5, 5), 11); // single element
    }

    #[test]
    fn test_update() {
        let mut fw = make_fw();
        fw.update(2, 5); // arr[2] += 5 → 10
        assert_eq!(fw.prefix_sum(5), 41);
        assert_eq!(fw.range_sum(0, 2), 14);
        assert_eq!(fw.range_sum(2, 4), 26);
    }

    #[test]
    fn test_single_element() {
        let mut fw = FenwickTree::new(1);
        fw.update(0, 42);
        assert_eq!(fw.prefix_sum(0), 42);
        assert_eq!(fw.range_sum(0, 0), 42);
    }

    #[test]
    fn test_set() {
        let mut fw = make_fw();
        fw.set(2, 10); // set arr[2] = 10 (was 5)
        assert_eq!(fw.range_sum(2, 2), 10);
        assert_eq!(fw.prefix_sum(5), 41);
    }
}

Deep Comparison

Fenwick Tree — Comparison

Core Insight

The Fenwick tree (BIT) is an implicit tree encoded in a 1-indexed array. The lowbit(i) = i & (-i) operation extracts the lowest set bit and drives both update (walk up: i += lowbit(i)) and query (walk down: i -= lowbit(i)). Simpler than a segment tree but more limited (prefix sums only, harder to generalize). Both languages implement exactly this bit trick.

OCaml Approach

• let lowbit i = i land (-i) — OCaml's bitwise AND

• i := !i + lowbit !i — mutable ref for loop counter

• let i = ref (i + 1) — convert 0-indexed to 1-indexed

• while !i <= fw.n do ... done — imperative loop

• Separate update (add delta) and prefix_sum functions

Rust Approach

• idx & (-idx) — Rust requires i64 for negation (usize can't be negative)

• let mut idx = (i + 1) as i64 — convert and use signed for arithmetic

• while idx > 0 { ... idx -= idx & (-idx) } — loop with mutable idx

• self.set() adds a convenience "set to value" operation

• from_slice constructor for batch initialization

Comparison Table

Aspect	OCaml	Rust
Lowbit	`i land (-i)`	`idx & (-idx)` (i64)
Index type	`int` (signed, 63-bit)	`i64` (for negation) then `usize`
Update loop	`i := !i + lowbit !i`	`idx += idx & (-idx)`
Query loop	`i := !i - lowbit !i`	`idx -= idx & (-idx)`
0→1 index	`let i = ref (i + 1)`	`let mut idx = (i + 1) as i64`
Delta update	`add delta` only	`update(delta)` + `set(value)`
Array access	`fw.tree.(!i)`	`self.tree[idx as usize]`

Exercises

Implement set(i, value): compute the current value with range_sum(i, i), then call update(i, value - current).

Build a Fenwick tree from a slice in O(n) using from_slice (n sequential updates) vs O(n log n) naive approach.

Implement find_kth(k) -> usize: find the leftmost position where prefix sum >= k using binary lifting on the Fenwick tree.

Implement a 2D Fenwick tree for range sum queries on a matrix.

Benchmark Fenwick tree vs segment tree for 1,000,000 random updates and prefix queries.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust