Lesson 46Advanced1h 2mAssessment-backed

Segment Tree and Range Queries

Answer repeated range queries and point updates without recomputing whole ranges.

What you will be able to do

Recognize when repeated range queries justify indexed aggregation.

Explain segment tree build, query, and update operations.

Implement range sum query with point update.

Compare segment trees with prefix sums and Fenwick trees.

Map range-query structures to dashboards, metrics, and inventory systems.

Prefix sums are excellent when data is static. Segment trees exist when the data changes and range answers must stay fast.

Ranges as a Tree

A segment tree stores an aggregate for a range at each node. Query combines only the nodes that exactly cover the requested range. Update changes one leaf and recomputes ancestors.

Segment tree storing range sums — Each internal node stores the aggregate of its child ranges.

Scenario: Metrics Dashboard

A usage dashboard must show revenue between arbitrary dates while corrections arrive throughout the day. Recomputing every requested date range is too slow; static prefix sums become stale after updates. A segment tree supports both.

Structure	Range query	Update	Best fit
Raw array	O(n)	O(1)	Rare queries.
Prefix sum	O(1)	O(n)	Static data.
Segment tree	O(log n)	O(log n)	Frequent queries and updates.
Fenwick tree	O(log n)	O(log n)	Prefix-friendly sums.

Segment tree query and point update flow — Updates climb upward; queries visit logarithmic cover nodes.

Same Pattern in Java, Python, and JavaScript

Range sum query with point update is the baseline segment tree implementation.

class NumArray {
    private final int n;
    private final int[] tree;
    NumArray(int[] nums) { n = nums.length; tree = new int[2 * n]; for (int i = 0; i < n; i++) tree[n + i] = nums[i]; for (int i = n - 1; i > 0; i--) tree[i] = tree[i * 2] + tree[i * 2 + 1]; }
    void update(int index, int value) { int i = index + n; tree[i] = value; for (i /= 2; i > 0; i /= 2) tree[i] = tree[i * 2] + tree[i * 2 + 1]; }
    int sumRange(int left, int right) { int sum = 0; for (int l = left + n, r = right + n; l <= r; l /= 2, r /= 2) { if ((l & 1) == 1) sum += tree[l++]; if ((r & 1) == 0) sum += tree[r--]; } return sum; }
}

Assessment trap

Do not use a segment tree when the data is static and prefix sums answer the product need more simply.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Support sumRange and update on an integer array.
For each number, count smaller numbers to its right.
Build a structure to return minimum value in a range with point updates.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Revenue dashboard	Sum every row for each date range.	Segment tree supports range query and correction updates.	Prefix sums may be simpler if data is immutable.
Inventory correction	Recompute warehouse totals after every correction.	Point update plus range aggregate avoids full recompute.	Validate inclusive range semantics.
SLA heatmap	Materialize every possible range.	Store aggregates by segment and combine cover nodes.	Memory and implementation complexity must be justified.

Solved modelInterview Question Solutions

Question 1: Range Sum Query Mutable

Support sumRange and update on an integer array. Segment tree stores range sums, so both point update and range query touch O(log n) tree nodes.

class NumArray {
    private final int n;
    private final int[] tree;
    NumArray(int[] nums) { n = nums.length; tree = new int[2 * n]; for (int i = 0; i < n; i++) tree[n + i] = nums[i]; for (int i = n - 1; i > 0; i--) tree[i] = tree[i * 2] + tree[i * 2 + 1]; }
    void update(int index, int value) { int i = index + n; tree[i] = value; for (i /= 2; i > 0; i /= 2) tree[i] = tree[i * 2] + tree[i * 2 + 1]; }
    int sumRange(int left, int right) { int sum = 0; for (int l = left + n, r = right + n; l <= r; l /= 2, r /= 2) { if ((l & 1) == 1) sum += tree[l++]; if ((r & 1) == 0) sum += tree[r--]; } return sum; }
}

Question 2: Count of Smaller Numbers After Self

For each number, count smaller numbers to its right. Coordinate-compress values, scan from right, query count below current rank, then update current rank.

import java.util.*;
class CountSmaller { int[] bit; List<Integer> countSmaller(int[] nums) { int[] sorted = nums.clone(); Arrays.sort(sorted); bit = new int[sorted.length + 2]; LinkedList<Integer> ans = new LinkedList<>(); for (int i = nums.length - 1; i >= 0; i--) { int rank = Arrays.binarySearch(sorted, nums[i]) + 1; ans.addFirst(sum(rank - 1)); add(rank, 1); } return ans; } void add(int i,int v){ for(;i<bit.length;i+=i&-i) bit[i]+=v; } int sum(int i){ int s=0; for(;i>0;i-=i&-i) s+=bit[i]; return s; } }

Question 3: Range Minimum Query

Build a structure to return minimum value in a range with point updates. Use the same segment tree shape but change the aggregate from sum to min and identity to infinity.

class RangeMin { int n; int[] tree; RangeMin(int[] a){ n=a.length; tree=new int[2*n]; java.util.Arrays.fill(tree,Integer.MAX_VALUE); for(int i=0;i<n;i++) tree[n+i]=a[i]; for(int i=n-1;i>0;i--) tree[i]=Math.min(tree[2*i],tree[2*i+1]); } int min(int l,int r){ int ans=Integer.MAX_VALUE; for(l+=n,r+=n;l<=r;l/=2,r/=2){ if((l&1)==1) ans=Math.min(ans,tree[l++]); if((r&1)==0) ans=Math.min(ans,tree[r--]); } return ans; } }

Solved modelWorked Interview Answer

Implement mutable range sum query with point updates. The segment tree stores range aggregates. Point updates rewrite one leaf and recompute ancestors; range queries combine logarithmic cover nodes.

class NumArray {
    private final int n;
    private final int[] tree;
    NumArray(int[] nums) { n = nums.length; tree = new int[2 * n]; for (int i = 0; i < n; i++) tree[n + i] = nums[i]; for (int i = n - 1; i > 0; i--) tree[i] = tree[i * 2] + tree[i * 2 + 1]; }
    void update(int index, int value) { int i = index + n; tree[i] = value; for (i /= 2; i > 0; i /= 2) tree[i] = tree[i * 2] + tree[i * 2 + 1]; }
    int sumRange(int left, int right) { int sum = 0; for (int l = left + n, r = right + n; l <= r; l /= 2, r /= 2) { if ((l & 1) == 1) sum += tree[l++]; if ((r & 1) == 0) sum += tree[r--]; } return sum; }
}

Hands-on drillTry It Yourself

Practice task

Build a segment tree for [2,4,5,7]. Query sum [1,3], then update index 2 to 10 and recompute affected nodes.

Failure patternsCommon Mistakes to Avoid

Using prefix sums when frequent updates exist.
Using segment tree when data is static and prefix sums are enough.
Off-by-one errors in inclusive ranges.
Forgetting to update ancestors.
Not naming aggregate function constraints.

Execution guardrailQuick-Start Checklist

Identify query type.
Check update frequency.
Define inclusive/exclusive range.
Build tree.
Query cover nodes.
Update leaf and ancestors.
State O(log n).

Recall drillKnowledge Check

Question	Strong answer
When use prefix sums?	Static range sums or rare updates.
When use segment tree?	Repeated range queries with updates.
What does an internal node store?	Aggregate answer for its covered range.

VocabularyKey Terms

Term	Meaning
Range query	Question over a contiguous interval.
Point update	Change one index.
Aggregate	Value such as sum/min/max stored for a range.
Cover node	Tree node fully inside query range.

Next practiceFurther Reading

Practice range sum query mutable, range minimum query, and lazy propagation later.
Compare Fenwick tree for prefix sums.
Review interval boundaries carefully.

Trie and Prefix Systems

Bit Manipulation