Handling Ranges Efficiently

Problem: Given an array nums, we want to repeatedly perform two operations:

  1. Update: Change nums[i] to val (Point Update) or change a range of values (Range Update).
  2. Query: Find the aggregate (sum, min, max) of the subarray nums[L...R].

The Real-World Scenario: A Real-Time Sales Dashboard

Imagine you are building a real-time sales dashboard for a global retail chain. The chain has thousands of stores.

  • Every time a sale is made, a store’s total revenue updates (Update).
  • The CEO frequently checks the total revenue across a specific range of stores, like “Stores 100 to 500 in the Midwest region” (Query).

If you use a simple Array:

  • Update: nums[i] += sale. This takes O(1).
  • Query: Loop from L to R to sum values. This takes O(N). When the CEO hits “Refresh”, the system iterates through thousands of stores, causing the dashboard to lag.

If you use a Prefix Sum Array:

  • Query: prefix[R] - prefix[L-1]. This takes O(1).
  • Update: If store 0 makes a sale, you must update the prefix sum for every subsequent store. This takes O(N). Now, the dashboard loads instantly, but every single sale across the globe freezes the database.

The Solution: We need a balanced data structure that can perform both operations in O(log N) time. Enter the Segment Tree and Fenwick Tree.

1. Segment Tree: The Hierarchy of Intervals

A Segment Tree is a full binary tree where each node represents an interval [L, R] and stores the aggregate value (e.g., sum) for that interval.

  • Root: Covers the entire array [0, N-1].
  • Leaves: Cover a single element [i, i].
  • Internal Nodes: Cover the merged range of their two children. If a node covers [L, R], its left child covers [L, Mid] and its right child covers [Mid+1, R].

Analogy: Think of it as a corporate hierarchy. The leaves are the individual stores. The parent nodes are district managers summarizing their stores’ sales. The higher you go, the more stores are summarized, up to the CEO (the root node) who sees the global total. When a store makes a sale, only their direct managers up the chain need to update their summaries—a logarithmic number of updates!

Interactive: Range Sum Visualizer

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

[0, 0, 0, 0, 0, 0, 0, 0]
Result: -

2. Segment Tree Implementation

The most common way to implement a Segment Tree is using a flattened 1D array (similar to a Binary Heap).

  • If a node is at index i, its left child is at 2 * i and its right child is at 2 * i + 1.
  • To safely accommodate all nodes, the size of the array is 4 * N (where N is the size of the original array).

Complete Code (Point Updates)

```java class SegmentTree { private int[] tree; private int n; public SegmentTree(int[] nums) { n = nums.length; tree = new int[4 * n]; if (n > 0) { build(nums, 1, 0, n - 1); } } private void build(int[] nums, int node, int start, int end) { if (start == end) { tree[node] = nums[start]; // Leaf node } else { int mid = start + (end - start) / 2; build(nums, 2 * node, start, mid); build(nums, 2 * node + 1, mid + 1, end); tree[node] = tree[2 * node] + tree[2 * node + 1]; // Aggregate } } 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; // Point update } else { int mid = start + (end - start) / 2; if (idx <= mid) { update(2 * node, start, mid, idx, val); // Go left } else { update(2 * node + 1, mid + 1, end, idx, val); // Go right } tree[node] = tree[2 * node] + tree[2 * node + 1]; // Re-aggregate } } 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; // Out of bounds, return identity (0 for sum, MAX_VALUE for min) } if (l <= start && end <= r) { return tree[node]; // Current interval is completely inside the query range } int mid = start + (end - start) / 2; int leftSum = query(2 * node, start, mid, l, r); int rightSum = query(2 * node + 1, mid + 1, end, l, r); return leftSum + rightSum; } } ```
```go type SegmentTree struct { tree []int n int } func NewSegmentTree(nums []int) *SegmentTree { n := len(nums) if n == 0 { return nil } st := &SegmentTree{ n: n, tree: make([]int, 4*n), } 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 - start) / 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 - start) / 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 // Out of bounds } if l <= start && end <= r { return st.tree[node] // Completely inside } mid := start + (end - start) / 2 leftSum := st.query(2*node, start, mid, l, r) rightSum := st.query(2*node+1, mid+1, end, l, r) return leftSum + rightSum } ```

3. Advanced: Lazy Propagation (Range Updates)

What if instead of updating a single index, we need to update an entire range at once? E.g., nums[L...R] += val. Updating N elements one-by-one using the point update method would take O(N log N).

Lazy Propagation solves this by deferring updates to descendants. Instead of pushing the update all the way down to the leaves immediately, we mark the current node with a “lazy” tag and return. The update is only pushed down (“propagated”) when a subsequent query or update actually needs to visit those descendant nodes.

  • Time Complexity for Range Update: O(log N)
  • Space Complexity: O(4N) for tree + O(4N) for lazy array

4. Fenwick Tree (Binary Indexed Tree)

While Segment Trees are incredibly flexible (supporting max, min, sum, multiplication), they are bulky, requiring O(4N) space and recursively traversing the tree.

Fenwick Trees provide an ultra-compact, bitwise alternative for scenarios where you specifically need Prefix Sums.

  • Space Complexity: O(N). It maps directly onto an array of size N + 1.
  • Time Complexity: O(log N) for Update and Query.
  • Limitation: It is strictly designed for commutative and invertible operations like Sum or Multiplication. Range Max/Min is extremely difficult to implement effectively.

The Bitwise Magic

A Fenwick Tree relies on the lowest set bit of an index to define intervals. The lowest set bit can be extracted using i & (-i) (due to Two’s Complement representation).

  • Query(index): To get the prefix sum up to index, you sum the values while iteratively removing the lowest set bit: index -= index & (-index).
  • Update(index, delta): To add delta to an element, you update its node and all “parents” that encompass it by continually adding the lowest set bit: index += index & (-index).

Fenwick Tree Implementation

```java class FenwickTree { private int[] bit; private int n; public FenwickTree(int n) { this.n = n; this.bit = new int[n + 1]; // 1-based indexing } public FenwickTree(int[] nums) { this(nums.length); for (int i = 0; i < nums.length; i++) { update(i, nums[i]); } } public void update(int index, int delta) { index++; // Convert to 1-based index while (index <= n) { bit[index] += delta; index += index & (-index); // Add lowest set bit } } public int query(int index) { index++; // Convert to 1-based index int sum = 0; while (index > 0) { sum += bit[index]; index -= index & (-index); // Remove lowest set bit } return sum; } public int queryRange(int left, int right) { return query(right) - query(left - 1); } } ```
```go type FenwickTree struct { bit []int n int } func NewFenwickTree(n int) *FenwickTree { return &FenwickTree{ bit: make([]int, n+1), n: n, } } func (ft *FenwickTree) Update(index int, delta int) { index++ // 1-based indexing for index <= ft.n { ft.bit[index] += delta index += index & (-index) // Add lowest set bit } } func (ft *FenwickTree) Query(index int) int { index++ // 1-based indexing sum := 0 for index > 0 { sum += ft.bit[index] index -= index & (-index) // Remove lowest set bit } return sum } func (ft *FenwickTree) QueryRange(left, right int) int { return ft.Query(right) - ft.Query(left-1) } ```

Summary: Segment Tree vs Fenwick Tree

Feature Segment Tree Fenwick Tree
Space Complexity O(4 * N) O(N)
Code Length Longer, recursive Extremely short, iterative
Flexibility High (Sum, Min, Max, Custom Objects) Low (Primarily Prefix Sums)
Range Updates Yes (via Lazy Propagation) Complex (requires 2 BITs for Range Update + Range Query)
Best Used For Complex aggregate queries, Range max/min Competitive programming speed, Memory-constrained environments

In technical interviews, Segment Trees are significantly more prevalent due to their flexibility, especially when dealing with Range Maximum/Minimum queries. However, knowing the Fenwick Tree’s i & (-i) trick is a massive flex that demonstrates deep systems-level understanding.