Handling Ranges Efficiently

Problem: Given an array nums, we want to:

1. Update: Change nums[i] to val.
2. Query: Find the sum of the subarray nums[L...R].

Approaches:

• Array: Update O(1), Query O(N). (Slow query)
• Prefix Sum: Update O(N), Query O(1). (Slow update)
• Segment Tree: Update O(log N), Query O(log N). (Balanced!)

1. Segment Tree

A full binary tree where each node represents an interval [L, R].

• Root: Covers [0, N-1].
• Left Child: Covers [L, Mid].
• Right Child: Covers [Mid+1, R].
• Value: Sum of the interval.

2. Interactive: Range Sum Visualizer

Update values and query ranges to see how the tree aggregates data.

[0, 0, 0, 0, 0, 0, 0, 0]

Result: -

3. Implementation (Segment Tree)

Java

class SegmentTree {
  int[] tree;
  int n;

  public SegmentTree(int[] nums) {
    n = nums.length;
    tree = new int[4 * n];
    build(nums, 1, 0, n - 1);
  }

  private void build(int[] nums, int node, int start, int end) {
    if (start == end) {
      tree[node] = nums[start];
    } else {
      int mid = (start + end) / 2;
      build(nums, 2 * node, start, mid);
      build(nums, 2 * node + 1, mid + 1, end);
      tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
  }

  public void update(int idx, int val) {
    update(1, 0, n - 1, idx, val);
  }

  private void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
      tree[node] = val;
    } else {
      int mid = (start + end) / 2;
      if (start <= idx && idx <= mid) update(2 * node, start, mid, idx, val);
      else update(2 * node + 1, mid + 1, end, idx, val);
      tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
  }

  public int query(int l, int r) {
    return query(1, 0, n - 1, l, r);
  }

  private int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r);
  }
}

Go

type SegmentTree struct {
  tree []int
  n    int
}

func NewSegmentTree(nums []int) *SegmentTree {
  st := &SegmentTree{
    n:    len(nums),
    tree: make([]int, 4*len(nums)),
  }
  st.build(nums, 1, 0, st.n-1)
  return st
}

func (st *SegmentTree) build(nums []int, node, start, end int) {
  if start == end {
    st.tree[node] = nums[start]
    return
  }
  mid := (start + end) / 2
  st.build(nums, 2*node, start, mid)
  st.build(nums, 2*node+1, mid+1, end)
  st.tree[node] = st.tree[2*node] + st.tree[2*node+1]
}

func (st *SegmentTree) Update(idx, val int) {
  st.update(1, 0, st.n-1, idx, val)
}

func (st *SegmentTree) update(node, start, end, idx, val int) {
  if start == end {
    st.tree[node] = val
    return
  }
  mid := (start + end) / 2
  if idx <= mid {
    st.update(2*node, start, mid, idx, val)
  } else {
    st.update(2*node+1, mid+1, end, idx, val)
  }
  st.tree[node] = st.tree[2*node] + st.tree[2*node+1]
}

func (st *SegmentTree) Query(l, r int) int {
  return st.query(1, 0, st.n-1, l, r)
}

func (st *SegmentTree) query(node, start, end, l, r int) int {
  if r < start || end < l { return 0 }
  if l <= start && end <= r { return st.tree[node] }
  mid := (start + end) / 2
  return st.query(2*node, start, mid, l, r) + st.query(2*node+1, mid+1, end, l, r)
}

4. Fenwick Tree (Binary Indexed Tree)

A compressed version using bit manipulation.

• Space: O(N) (vs O(4N) for SegTree).
• Logic: index += index & (-index) to climb up.
• Limitation: Range Sums are easy (Prefix Sums), Range Max/Min is hard.

Use Segment Tree for flexibility, Fenwick for coding speed and space.