Segment Tree and Fenwick Tree

When an array is modified dynamically alongside range queries, a static prefix sum array requires $O(n)$ time to rebuild on every point update. A Fenwick Tree (Binary Indexed Tree / BIT) and a Segment Tree support both point updates and arbitrary range queries in $O(\log n)$ time.

Choosing Between Prefix Sum, Fenwick Tree, and Segment Tree:

  Static Array (0 Updates):
    ---> Prefix Sum (`O(n)` build, `O(1)` range query)

  Dynamic Point Add + Prefix/Range Sum (Invertible Operation `+`, `^`):
    ---> Fenwick Tree / BIT (`1 * N` array, tiny 15-line code, fastest `O(log n)` constant!)

  Dynamic Point Set + Arbitrary Associative Monoid (`min`, `max`, `gcd`, matrix mul):
    ---> Iterative Segment Tree (`2 * N` flat array, `O(log n)` update & range query!)

1. Fenwick Tree (Binary Indexed Tree) in 25 Lines of Rust

A Fenwick Tree uses 1-based indexing (1..=n) where each index i aggregates a block of length i & i.wrapping_neg() (the lowest set bit of i, i.e., i & -i in two's-complement):

• Update (add): Adds i & i.wrapping_neg() to i until i > n.
• Prefix Sum (prefix_sum): Subtracts i & i.wrapping_neg() (i &= i - 1) from i until i == 0.

pub struct FenwickTree {
    tree: Vec<i64>,
}

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

    /// Adds `delta` to 0-based index `idx` in O(log n) time.
    #[inline]
    pub fn add(&mut self, idx: usize, delta: i64) {
        let mut i = idx + 1; // Convert to 1-based index
        while i < self.tree.len() {
            self.tree[i] += delta;
            i += i & i.wrapping_neg(); // Add lowest set bit (`i & -i`)
        }
    }

    /// Returns the prefix sum of `arr[0..end_exclusive]` in O(log n) time.
    #[inline]
    pub fn prefix_sum(&self, end_exclusive: usize) -> i64 {
        let mut sum = 0i64;
        let mut i = end_exclusive;
        while i > 0 {
            sum += self.tree[i];
            i &= i - 1; // Clear lowest set bit
        }
        sum
    }

    /// Returns the range sum of `arr[left..right_exclusive]` in O(log n) time.
    #[inline]
    pub fn range_sum(&self, left: usize, right_exclusive: usize) -> i64 {
        self.prefix_sum(right_exclusive) - self.prefix_sum(left)
    }
}

2. Iterative Flat-Array Segment Tree ($2N$ Memory, Any Monoid)

Unlike a Fenwick Tree (which requires an invertible operation like + to compute prefix(r) - prefix(l)), a Segment Tree supports non-invertible associative operations such as Range Minimum / Maximum Query (RMQ), greatest common divisor (gcd), or matrix multiplication.

Using an iterative bottom-up layout stores all leaves at indices n..2*n and internal parent nodes at 1..n—requiring only 2 * n elements (instead of 4 * n for recursive trees) and zero recursion:

/// Iterative Segment Tree supporting O(log n) point updates and O(log n) range maximum queries.
pub struct MaxSegmentTree {
    n: usize,
    tree: Vec<i64>,
}

impl MaxSegmentTree {
    pub fn from_slice(values: &[i64]) -> Self {
        let n = values.len();
        let mut tree = vec![i64::MIN; 2 * n];
        // Copy leaves into indices `n .. 2*n`:
        tree[n..2 * n].copy_from_slice(values);
        // Build internal nodes bottom-up from `n - 1` down to `1`:
        for i in (1..n).rev() {
            tree[i] = tree[2 * i].max(tree[2 * i + 1]);
        }
        Self { n, tree }
    }

    /// Sets `arr[idx] = val` in O(log n) time.
    pub fn update(&mut self, mut idx: usize, val: i64) {
        idx += self.n;
        self.tree[idx] = val;
        while idx > 1 {
            idx >>= 1;
            self.tree[idx] = self.tree[2 * idx].max(self.tree[2 * idx + 1]);
        }
    }

    /// Queries the maximum in half-open range `[left..right]` in O(log n) time.
    pub fn query_max(&self, mut left: usize, mut right: usize) -> i64 {
        let mut res = i64::MIN;
        left += self.n;
        right += self.n;

        while left < right {
            if (left & 1) == 1 {
                res = res.max(self.tree[left]);
                left += 1;
            }
            if (right & 1) == 1 {
                right -= 1;
                res = res.max(self.tree[right]);
            }
            left >>= 1;
            right >>= 1;
        }
        res
    }
}

fn main() {
    let mut bit = FenwickTree::new(5);
    for (i, &v) in [10, 20, 30, 40, 50].iter().enumerate() {
        bit.add(i, v);
    }
    assert_eq!(bit.range_sum(1, 4), 20 + 30 + 40);
    bit.add(2, 5); // arr[2] becomes 35
    assert_eq!(bit.range_sum(1, 4), 20 + 35 + 40);

    let mut seg = MaxSegmentTree::from_slice(&[12, 45, 7, 30, 19]);
    assert_eq!(seg.query_max(0, 5), 45);
    seg.update(1, 10); // Replace 45 with 10
    assert_eq!(seg.query_max(0, 5), 30);

    println!(
        "Fenwick range sum [1..4): {}, SegmentTree max [0..5): {}",
        bit.range_sum(1, 4),
        seg.query_max(0, 5)
    );
}

Fenwick range sum [1..4): 95, SegmentTree max [0..5): 30