Handling Ranges Efficiently

[!NOTE] This module explores the core principles of Segment and Fenwick Trees, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Problem: Given an array nums, efficiently handle updates and range queries.

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

Segment Tree: A 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: Aggregate (Sum, Min, Max) of the interval.

Complexity: Update O(log N), Query O(log N).

2. Interactive Analysis

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

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

Result: -

3. Intuition

Why trees?

Array: Update O(1), Query O(N) (sum loop).
Prefix Sum: Update O(N) (rebuild array), Query O(1).
Segment Tree: Both O(log N). We decompose the range into pre-calculated chunks. For [0-7], if we want sum [0-3], that’s just the left child of the root.

4. Implementation

Segment Tree

Java

```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)
}
```

5. Complexity Analysis

Strategy	Update	Query	Space	Notes
Segment Tree	O(log N)	O(log N)	O(4N)	Supports Sum, Min, Max, etc.
Fenwick Tree	O(log N)	O(log N)	O(N)	Faster constant, harder logic.

Segment & Fenwick Trees