Stage 4: Advanced Techniques·Segment Tree & BIT

Medium#30710 min readSegment TreeBITPrefix SumsLeetCode

Range Sum Query - Mutable

Binary Indexed Tree (Fenwick)

Classic segment tree. Build, update, query. Implement from scratch in Rust.

Published Apr 16, 2026

Problem

Implement a NumArray class that supports two operations on an integer array, each in sub-linear time:

update(i, val) — set nums[i] to val.
sumRange(l, r) — return sum(nums[l..=r]) inclusive.

Naive reads are O(n). Naive writes with a prefix-sum cache are O(n) because a single update invalidates every downstream prefix. The problem wants both in O(log n).

Input

["NumArray","sumRange","update","sumRange"], [[[1,3,5]],[0,2],[1,2],[0,2]]

Output

[null, 9, null, 8]

Explanation

Initial [1,3,5] sums to 9. After nums[1]=2, array is [1,2,5], which sums to 8.

Input

["NumArray","sumRange","sumRange","update","sumRange"], [[[0,9,5,7,3]],[4,4],[2,4],[4,5],[3,3]]

Output

[null, 3, 15, null, 7]

Intuition

Two extremes clarify the shape of the problem.

Store raw values. Range sum costs O(n) per query; updates are O(1).
Store prefix sums. Queries collapse to prefix[r+1] - prefix[l], but one update has to rewrite n prefix entries.

Both hit a wall when queries and updates mix at scale. The fix is to split the prefix into log n overlapping chunks arranged in a tree. Each position is covered by O(log n) nodes, so both operations climb the tree in O(log n) steps.

Two classical data structures implement this idea with different flavors:

Fenwick Tree / BIT — implicit binary tree, indices derived from the lowest set bit. Smallest code, fastest in practice for sum-like associative ops.
Segment Tree — explicit tree over intervals, generalizes to min/max/gcd/lazy propagation. More boilerplate, more reach.

For raw update + sumRange, the BIT is the tightest fit. We show both so you can reach for the right tool later.

Approach

Naive Array

TimeO(n) per query

SpaceO(n)

Store the array directly. update is trivial; sumRange iterates. Fine for tiny inputs and useful as a correctness oracle.

pub struct NumArray {
    nums: Vec<i32>,
}

impl NumArray {
    pub fn new(nums: Vec<i32>) -> Self {
        Self { nums }
    }

    pub fn update(&mut self, i: i32, val: i32) {
        self.nums[i as usize] = val;
    }

    pub fn sum_range(&self, l: i32, r: i32) -> i32 {
        self.nums[l as usize..=r as usize].iter().sum()
    }
}

Rust · runnable

class NumArray {
  private nums: number[];

  constructor(nums: number[]) {
    this.nums = nums.slice();
  }

  update(i: number, val: number): void {
    this.nums[i] = val;
  }

  sumRange(l: number, r: number): number {
    let total = 0;
    for (let k = l; k <= r; k++) total += this.nums[k];
    return total;
  }
}

TypeScript · runnable

Binary Indexed Tree

TimeO(log n) per op

SpaceO(n)

Recommended

A BIT stores partial sums indexed by the lowest set bit of the index. For 1-based index i, node i covers i - (i & -i) + 1 ..= i.

prefix(i) = sum of nums[0..i]: keep subtracting i & -i from i and accumulating.
add(i, delta): propagate delta up — i += i & -i — until past the end.
update(i, val) becomes add(i, val - old[i]). We keep a mirror of the raw values to compute the delta.
sumRange(l, r) = prefix(r+1) - prefix(l).

Each index has at most log2(n) lowest-bit hops, so every operation is O(log n).

pub struct NumArray {
    n: usize,
    raw: Vec<i32>,
    bit: Vec<i64>, // 1-indexed; bit[0] unused
}

impl NumArray {
    pub fn new(nums: Vec<i32>) -> Self {
        let n = nums.len();
        let mut s = Self {
            n,
            raw: vec![0; n],
            bit: vec![0; n + 1],
        };
        for (i, &v) in nums.iter().enumerate() {
            s.update(i as i32, v);
        }
        s
    }

    pub fn update(&mut self, i: i32, val: i32) {
        let idx = i as usize;
        let delta = (val - self.raw[idx]) as i64;
        self.raw[idx] = val;
        let mut j = idx + 1; // to 1-based
        while j <= self.n {
            self.bit[j] = delta;
            j = j & j.wrapping_neg();
        }
    }

    pub fn sum_range(&self, l: i32, r: i32) -> i32 {
        (self.prefix((r + 1) as usize) - self.prefix(l as usize)) as i32
    }
}

impl NumArray {
    fn prefix(&self, mut i: usize) -> i64 {
        let mut s = 0i64;
        while i > 0 {
            s += self.bit[i];
            i -= i & i.wrapping_neg();
        }
        s
    }
}

Rust · runnable

class NumArray {
  private n: number;
  private raw: number[];
  private bit: number[]; // 1-indexed; bit[0] unused

  constructor(nums: number[]) {
    this.n = nums.length;
    this.raw = new Array(this.n).fill(0);
    this.bit = new Array(this.n + 1).fill(0);
    for (let i = 0; i < this.n; i++) this.update(i, nums[i]);
  }

  update(i: number, val: number): void {
    const delta = val - this.raw[i];
    this.raw[i] = val;
    for (let j = i + 1; j <= this.n; j += j & -j) {
      this.bit[j] += delta;
    }
  }

  sumRange(l: number, r: number): number {
    return this.prefix(r + 1) - this.prefix(l);
  }

  private prefix(i: number): number {
    let s = 0;
    for (; i > 0; i -= i & -i) s += this.bit[i];
    return s;
  }
}

TypeScript · runnable

The j & -j trick isolates the lowest set bit — the idiom that makes the whole structure work. Note the j.wrapping_neg() in Rust to keep unsigned arithmetic lawful.

Iterative Segment Tree

TimeO(log n) per op

SpaceO(n)

A power-of-two-sized segment tree stored in a flat array. Leaves occupy tree[n .. 2n]; each internal node is the sum of its two children. Point update walks from a leaf to the root; range query walks inward from both endpoints.

Heavier than a BIT for pure sums, but the skeleton generalizes — swap + for min, max, gcd, and you have a universal tool. Understand this one and #699 / #2407 become exercises.

pub struct NumArray {
    n: usize,
    tree: Vec<i64>,
}

impl NumArray {
    pub fn new(nums: Vec<i32>) -> Self {
        let n = nums.len();
        let mut tree = vec![0i64; 2 * n.max(1)];
        for (i, &v) in nums.iter().enumerate() {
            tree[n + i] = v as i64;
        }
        for i in (1..n).rev() {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
        Self { n, tree }
    }

    pub fn update(&mut self, i: i32, val: i32) {
        let mut p = self.n + i as usize;
        self.tree[p] = val as i64;
        p /= 2;
        while p >= 1 {
            self.tree[p] = self.tree[2 * p] + self.tree[2 * p + 1];
            p /= 2;
        }
    }

    pub fn sum_range(&self, l: i32, r: i32) -> i32 {
        let mut l = self.n + l as usize;
        let mut r = self.n + r as usize + 1;
        let mut s = 0i64;
        while l < r {
            if l & 1= 1 { s = self.tree[l]; l = 1; }
            if r & 1= 1 { r -= 1; s = self.tree[r]; }
            l = 2;
            r = 2;
        }
        s as i32
    }
}

Rust · runnable

class NumArray {
  private n: number;
  private tree: number[];

  constructor(nums: number[]) {
    this.n = Math.max(nums.length, 1);
    this.tree = new Array(2 * this.n).fill(0);
    for (let i = 0; i < nums.length; i++) this.tree[this.n + i] = nums[i];
    for (let i = this.n - 1; i >= 1; i--) {
      this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
    }
  }

  update(i: number, val: number): void {
    let p = this.n + i;
    this.tree[p] = val;
    for (p = p >> 1; p >= 1; p = p >> 1) {
      this.tree[p] = this.tree[2 * p] + this.tree[2 * p + 1];
    }
  }

  sumRange(l: number, r: number): number {
    let lo = this.n + l;
    let hi = this.n + r + 1;
    let sum = 0;
    while (lo < hi) {
      if (lo & 1) { sum += this.tree[lo]; lo++; }
      if (hi & 1) { hi--; sum += this.tree[hi]; }
      lo >>= 1;
      hi >>= 1;
    }
    return sum;
  }
}

TypeScript · runnable

Trace

BIT state after NumArray([1, 3, 5]). Indices are 1-based; bit[j] covers j - lowbit(j) + 1 ..= j.

j	binary	lowbit	covers	value
1	001	1	[1..=1]	1
2	010	2	[1..=2]	1 + 3 = 4
3	011	1	[3..=3]	5

Query sumRange(0, 2) = prefix(3) - prefix(0):

prefix(3): bit[3] = 5, then 3 - 1 = 2, bit[2] = 4, then 2 - 2 = 0. Total 9.
prefix(0) = 0.
Range sum is 9.

Now update(1, 2): delta = 2 - 3 = -1. Walk j = 2, 3... wait, from j = 2 we add j & -j = 2, giving j = 4 > n. So we update only bit[2] += -1 → bit[2] = 3. Query sumRange(0, 2) again: prefix(3) = bit[3] + bit[2] = 5 + 3 = 8. Correct — the new array [1, 2, 5] sums to 8.

Edge cases

Single element — BIT of size 1 works; update walks one step, queries return the lone value.
All zeros — tree is all zeros; updates still propagate correctly via deltas.
Large deltas — use i64 internally to avoid overflow when summing many i32 values. The LeetCode constraints are tight, but production code should pick width based on expected sum range.
Out-of-order queries — every operation is independent; mix update / sumRange in any order.

💡

Tip

For range update + range sum, use two BITs (one for the delta, one for the cross term). For range update + point query, one BIT over the difference array is enough. The Fenwick family goes much deeper than this problem needs.

Takeaway

Any associative aggregate over a mutable sequence wants a tree-of-partial-sums. BITs cover +, segment trees handle min / max / custom monoids. Both give you O(log n) per operation — the baseline for production-scale time-series analytics, order book aggregation, and live dashboards over mutable data.

Memorize the j & -j trick, the iterative segment-tree skeleton, and their cost model. They surface in #315, #699, #2407, and in real systems any time you need "running statistics that update constantly."

Hard#315

Count of Smaller Numbers After Self

BIT or merge sort. Process right to left, count elements smaller than current.

Hard#699

Falling Squares

Coordinate compression + lazy propagation. A complete segment tree exercise.

Hard#2407

Longest Increasing Subsequence II

Segment tree optimization on DP transitions. The ‘DP + data structure’ pattern.