Segment Tree Interview Questions
Last updated 2026-11-19
A segment tree answers range queries, such as the sum, minimum or maximum over a slice, and applies point or range updates, all in O(log n). It sits between a plain array, with O(1) update but O(n) query, and a prefix-sum array, with the reverse trade-off.
The problems here move from the basic sum and minimum trees to lazy propagation and nodes that carry several values. Each shows Python and Java code with complexity and edge cases. A lighter structure for sums only is covered in Fenwick tree interview questions, and the divide and conquer thinking behind the recursion is in divide and conquer interview questions.
| Build | O(n) |
|---|---|
| Point update and range query | O(log n) |
| Range update | O(log n) with lazy propagation |
| Operation requirement | Associative merge function |
The pattern and when to spot it
Use a segment tree when the array changes and you must repeatedly query ranges. If the array never changes, a prefix sum or a sparse table is simpler. Typical wording: update the value at an index, then answer the sum or minimum between two indices, many times, with n and q up to 10^5.
The structure works for any operation that can merge two halves: sum, min, max, gcd, or a tuple such as the best subarray. Pick the identity element first, for example 0 for sum and infinity for min. Two layouts exist: the recursive one with a 4n array, which supports lazy propagation and descents, and the bottom-up iterative one with a 2n array, which is shorter for point update and range query.
Common pitfalls
- Allocating fewer than 4n slots for a recursive tree, which fails for sizes that are not powers of two.
- Mixing inclusive and half-open ranges between the update and query code.
- Forgetting to push lazy values down before recursing into children.
- Using a non-commutative merge with the iterative bottom-up query, which needs separate left and right accumulators.
- Overflowing int in range sums. Use long when values or counts can be large.
Segment Tree Interview Questions: questions with worked answers
1 Range sum query with point updates (bottom-up segment tree)
easyStore the array in the leaves tree[n..2n-1] and each parent as the sum of its two children. A point update rewrites the leaf and walks up recomputing parents. A query over [l, r) climbs from both ends, taking a node whenever the boundary is a right child on the left side, or a left child on the right side. Time O(n) build, O(log n) update and query, space O(n). Edge cases: empty range returns 0, l equal to r, update to the same value, n not a power of two (the bottom-up layout still works for sums).
pythonclass NumArray: def __init__(self, nums): self.n = len(nums) self.t = [0] * self.n + list(nums) for i in range(self.n - 1, 0, -1): self.t[i] = self.t[2 * i] + self.t[2 * i + 1] def update(self, i, val): i += self.n self.t[i] = val while i > 1: i >>= 1 self.t[i] = self.t[2 * i] + self.t[2 * i + 1] def sum_range(self, left, right): # inclusive l, r, res = left + self.n, right + self.n + 1, 0 while l < r: if l & 1: res += self.t[l]; l += 1 if r & 1: r -= 1; res += self.t[r] l >>= 1; r >>= 1 return resjavaclass NumArray { private final int n; private final int[] t; NumArray(int[] nums) { n = nums.length; t = new int[2 * n]; System.arraycopy(nums, 0, t, n, n); for (int i = n - 1; i > 0; i--) t[i] = t[2 * i] + t[2 * i + 1]; } void update(int i, int val) { i += n; t[i] = val; while (i > 1) { i >>= 1; t[i] = t[2 * i] + t[2 * i + 1]; } } int sumRange(int left, int right) { int l = left + n, r = right + n + 1, res = 0; while (l < r) { if ((l & 1) == 1) res += t[l++]; if ((r & 1) == 1) res += t[--r]; l >>= 1; r >>= 1; } return res; } }2 Range minimum query with updates
easyThe same layout works for any associative operation. Replace sum with min and use infinity as the identity for empty ranges. Use this when a sparse table would be fine for static data but values change. Time O(log n) per operation, space O(n). Edge cases: identity element for empty ranges, updates that raise a minimum (parents must be recomputed, not just compared), l greater than r.
pythonINF = float('inf') class RMQ: def __init__(self, a): self.n = len(a) self.t = [INF] * self.n + list(a) for i in range(self.n - 1, 0, -1): self.t[i] = min(self.t[2 * i], self.t[2 * i + 1]) def update(self, i, v): i += self.n self.t[i] = v while i > 1: i >>= 1 self.t[i] = min(self.t[2 * i], self.t[2 * i + 1]) def query(self, l, r): # inclusive l += self.n; r += self.n + 1 res = INF while l < r: if l & 1: res = min(res, self.t[l]); l += 1 if r & 1: r -= 1; res = min(res, self.t[r]) l >>= 1; r >>= 1 return resjavaclass RMQ { private final int n; private final int[] t; RMQ(int[] a) { n = a.length; t = new int[2 * n]; System.arraycopy(a, 0, t, n, n); for (int i = n - 1; i > 0; i--) t[i] = Math.min(t[2 * i], t[2 * i + 1]); } void update(int i, int v) { i += n; t[i] = v; while (i > 1) { i >>= 1; t[i] = Math.min(t[2 * i], t[2 * i + 1]); } } int query(int l, int r) { int res = Integer.MAX_VALUE; for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { if ((l & 1) == 1) res = Math.min(res, t[l++]); if ((r & 1) == 1) res = Math.min(res, t[--r]); } return res; } }3 Range GCD queries with updates
easyGreatest common divisor is associative and gcd(0, x) = x, so 0 is the identity. Build the bottom-up tree with gcd as the merge and answer range queries the same way as for sums. Each merge costs O(log max value), so a query is O(log n * log V). Time O(log n * log V) per operation, space O(n). Edge cases: a range containing only zeros (gcd 0), negative numbers (use absolute values), single element ranges.
pythonfrom math import gcd class GcdTree: def __init__(self, a): self.n = len(a) self.t = [0] * self.n + list(a) for i in range(self.n - 1, 0, -1): self.t[i] = gcd(self.t[2 * i], self.t[2 * i + 1]) def update(self, i, v): i += self.n self.t[i] = v while i > 1: i >>= 1 self.t[i] = gcd(self.t[2 * i], self.t[2 * i + 1]) def query(self, l, r): # inclusive l += self.n; r += self.n + 1 g = 0 while l < r: if l & 1: g = gcd(g, self.t[l]); l += 1 if r & 1: r -= 1; g = gcd(g, self.t[r]) l >>= 1; r >>= 1 return gjavaclass GcdTree { private final int n; private final int[] t; GcdTree(int[] a) { n = a.length; t = new int[2 * n]; System.arraycopy(a, 0, t, n, n); for (int i = n - 1; i > 0; i--) t[i] = gcd(t[2 * i], t[2 * i + 1]); } private static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } void update(int i, int v) { i += n; t[i] = v; while (i > 1) { i >>= 1; t[i] = gcd(t[2 * i], t[2 * i + 1]); } } int query(int l, int r) { int g = 0; for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { if ((l & 1) == 1) g = gcd(g, t[l++]); if ((r & 1) == 1) g = gcd(g, t[--r]); } return g; } }4 Kth smallest in a dynamic multiset of small integers
mediumIndex a segment tree by value and store counts. Insert or remove by updating a leaf. To find the kth smallest, descend from the root: if the left child count is at least k go left, otherwise subtract it from k and go right. Use a power-of-two size so children of node i are 2i and 2i+1. Time O(log N) per operation, space O(N) for value range N. Edge cases: k larger than the total count (check first), removing a value that is not present, duplicates, values outside the range.
pythonclass KthSet: def __init__(self, maxv): self.size = 1 while self.size < maxv: self.size *= 2 self.t = [0] * (2 * self.size) def add(self, x, d=1): i = x + self.size while i >= 1: self.t[i] += d i >>= 1 def kth(self, k): # 1-based node = 1 while node < self.size: if self.t[2 * node] >= k: node = 2 * node else: k -= self.t[2 * node] node = 2 * node + 1 return node - self.sizejavaclass KthSet { private final int size; private final int[] t; KthSet(int maxv) { int s = 1; while (s < maxv) s *= 2; size = s; t = new int[2 * s]; } void add(int x, int d) { for (int i = x + size; i >= 1; i >>= 1) t[i] += d; } int kth(int k) { int node = 1; while (node < size) { if (t[2 * node] >= k) node = 2 * node; else { k -= t[2 * node]; node = 2 * node + 1; } } return node - size; } }5 First index at or after a position whose value is at least x
mediumStore the maximum of each range. Descend recursively: skip a node whose maximum is below x, otherwise go left first and fall back to the right. Because whole subtrees are pruned by their maximum, the search is O(log n) per query when you also respect the lower bound L. Time O(log n) per query, space O(n). Edge cases: no such index (return -1), L beyond the end, equal values, array of length 1.
pythonclass FirstAtLeast: def __init__(self, a): self.n = len(a) self.t = [0] * (4 * self.n) self._build(1, 0, self.n - 1, a) def _build(self, node, lo, hi, a): if lo == hi: self.t[node] = a[lo]; return mid = (lo + hi) // 2 self._build(2 * node, lo, mid, a) self._build(2 * node + 1, mid + 1, hi, a) self.t[node] = max(self.t[2 * node], self.t[2 * node + 1]) def find(self, L, x, node=1, lo=0, hi=None): if hi is None: hi = self.n - 1 if hi < L or self.t[node] < x: return -1 if lo == hi: return lo mid = (lo + hi) // 2 r = self.find(L, x, 2 * node, lo, mid) return r if r != -1 else self.find(L, x, 2 * node + 1, mid + 1, hi)javaclass FirstAtLeast { private final int n; private final int[] t; FirstAtLeast(int[] a) { n = a.length; t = new int[4 * n]; build(1, 0, n - 1, a); } private void build(int node, int lo, int hi, int[] a) { if (lo == hi) { t[node] = a[lo]; return; } int mid = (lo + hi) / 2; build(2 * node, lo, mid, a); build(2 * node + 1, mid + 1, hi, a); t[node] = Math.max(t[2 * node], t[2 * node + 1]); } int find(int L, int x) { return find(L, x, 1, 0, n - 1); } private int find(int L, int x, int node, int lo, int hi) { if (hi < L || t[node] < x) return -1; if (lo == hi) return lo; int mid = (lo + hi) / 2; int r = find(L, x, 2 * node, lo, mid); return r != -1 ? r : find(L, x, 2 * node + 1, mid + 1, hi); } }6 Count inversions using a segment tree
mediumAn inversion is a pair i < j with a[i] > a[j]. Compress values to ranks 0..m-1. Scan left to right: for each element, add the number of already inserted values with a greater rank (a range-sum query), then insert it with a point update. Time O(n log n), space O(n). Edge cases: duplicates are not inversions (use strictly greater ranks), already sorted input (0), reverse sorted input gives n(n-1)/2 so use long.
pythondef count_inversions(a): ranks = {v: i for i, v in enumerate(sorted(set(a)))} m = len(ranks) t = [0] * (2 * m) def add(i): i += m while i >= 1: t[i] += 1 i >>= 1 def query(l, r): # [l, r) l += m; r += m res = 0 while l < r: if l & 1: res += t[l]; l += 1 if r & 1: r -= 1; res += t[r] l >>= 1; r >>= 1 return res inv = 0 for x in a: k = ranks[x] inv += query(k + 1, m) add(k) return invjavalong countInversions(int[] a) { int[] sorted = Arrays.stream(a).distinct().sorted().toArray(); int m = sorted.length; int[] t = new int[2 * m]; long inv = 0; for (int x : a) { int k = Arrays.binarySearch(sorted, x); for (int l = k + 1 + m, r = 2 * m; l < r; l >>= 1, r >>= 1) { if ((l & 1) == 1) inv += t[l++]; if ((r & 1) == 1) inv += t[--r]; } for (int i = k + m; i >= 1; i >>= 1) t[i]++; } return inv; }7 Count of smaller numbers after self
mediumFor each element count how many later elements are strictly smaller. Compress values, scan from right to left, query the count of ranks below the current rank and then insert the current rank. Results are stored by original position. Time O(n log n), space O(n). Edge cases: duplicates (strict smaller only, so query ranks below), negative values, single element gives 0.
pythondef count_smaller(nums): ranks = {v: i for i, v in enumerate(sorted(set(nums)))} m = len(ranks) t = [0] * (2 * m) res = [0] * len(nums) for idx in range(len(nums) - 1, -1, -1): k = ranks[nums[idx]] l, r, c = m, k + m, 0 l = m # range [0, k) while l < r: if l & 1: c += t[l]; l += 1 if r & 1: r -= 1; c += t[r] l >>= 1; r >>= 1 res[idx] = c i = k + m while i >= 1: t[i] += 1 i >>= 1 return resjavaList<Integer> countSmaller(int[] nums) { int[] sorted = Arrays.stream(nums).distinct().sorted().toArray(); int m = sorted.length; int[] t = new int[2 * m]; Integer[] res = new Integer[nums.length]; for (int idx = nums.length - 1; idx >= 0; idx--) { int k = Arrays.binarySearch(sorted, nums[idx]); int c = 0; for (int l = m, r = k + m; l < r; l >>= 1, r >>= 1) { if ((l & 1) == 1) c += t[l++]; if ((r & 1) == 1) c += t[--r]; } res[idx] = c; for (int i = k + m; i >= 1; i >>= 1) t[i]++; } return Arrays.asList(res); }8 Longest increasing subsequence using a max segment tree
mediumProcess elements in order. For value x, the best subsequence ending at x is 1 plus the maximum dp over smaller values seen so far, which is a range-maximum query over ranks below x. Store that result at the rank of x with a point update using max. The answer is the largest dp. Time O(n log n), space O(n). Edge cases: strict versus non-decreasing (query ranks below for strict), duplicates updating the same leaf with a max, empty input returns 0.
pythondef lis(nums): ranks = {v: i for i, v in enumerate(sorted(set(nums)))} m = len(ranks) t = [0] * (2 * m) best = 0 for x in nums: k = ranks[x] l, r, res = m, k + m, 0 while l < r: if l & 1: res = max(res, t[l]); l += 1 if r & 1: r -= 1; res = max(res, t[r]) l >>= 1; r >>= 1 d = res + 1 best = max(best, d) i = k + m t[i] = max(t[i], d) while i > 1: i >>= 1 t[i] = max(t[2 * i], t[2 * i + 1]) return bestjavaint lis(int[] nums) { int[] sorted = Arrays.stream(nums).distinct().sorted().toArray(); int m = sorted.length; int[] t = new int[2 * m]; int best = 0; for (int x : nums) { int k = Arrays.binarySearch(sorted, x); int res = 0; for (int l = m, r = k + m; l < r; l >>= 1, r >>= 1) { if ((l & 1) == 1) res = Math.max(res, t[l++]); if ((r & 1) == 1) res = Math.max(res, t[--r]); } int d = res + 1; best = Math.max(best, d); int i = k + m; t[i] = Math.max(t[i], d); while (i > 1) { i >>= 1; t[i] = Math.max(t[2 * i], t[2 * i + 1]); } } return best; }9 Range add and range sum with lazy propagation
hardA range update touches many leaves, so mark a covering node with a pending add (lazy) instead of updating below it. Before descending into a node, push its pending value to the children. A node fully inside the range updates its sum by value times length and stores the lazy tag. Queries push down on the way. Time O(log n) per update and query, space O(n). Edge cases: forgetting to push the lazy value before recursing, a lazy value multiplied by segment length rather than 1, overlapping updates accumulating, large sums needing long.
pythonclass LazySeg: def __init__(self, a): self.n = len(a) self.s = [0] * (4 * self.n) self.lz = [0] * (4 * self.n) self._build(1, 0, self.n - 1, a) def _build(self, o, lo, hi, a): if lo == hi: self.s[o] = a[lo]; return m = (lo + hi) // 2 self._build(2 * o, lo, m, a) self._build(2 * o + 1, m + 1, hi, a) self.s[o] = self.s[2 * o] + self.s[2 * o + 1] def _push(self, o, lo, hi): if self.lz[o]: m = (lo + hi) // 2 for c, a, b in ((2 * o, lo, m), (2 * o + 1, m + 1, hi)): self.s[c] += self.lz[o] * (b - a + 1) self.lz[c] += self.lz[o] self.lz[o] = 0 def add(self, l, r, v, o=1, lo=0, hi=None): if hi is None: hi = self.n - 1 if r < lo or hi < l: return if l <= lo and hi <= r: self.s[o] += v * (hi - lo + 1) self.lz[o] += v return self._push(o, lo, hi) m = (lo + hi) // 2 self.add(l, r, v, 2 * o, lo, m) self.add(l, r, v, 2 * o + 1, m + 1, hi) self.s[o] = self.s[2 * o] + self.s[2 * o + 1] def sum(self, l, r, o=1, lo=0, hi=None): if hi is None: hi = self.n - 1 if r < lo or hi < l: return 0 if l <= lo and hi <= r: return self.s[o] self._push(o, lo, hi) m = (lo + hi) // 2 return self.sum(l, r, 2 * o, lo, m) + self.sum(l, r, 2 * o + 1, m + 1, hi)javaclass LazySeg { private final int n; private final long[] s, lz; LazySeg(int[] a) { n = a.length; s = new long[4 * n]; lz = new long[4 * n]; build(1, 0, n - 1, a); } private void build(int o, int lo, int hi, int[] a) { if (lo == hi) { s[o] = a[lo]; return; } int m = (lo + hi) / 2; build(2 * o, lo, m, a); build(2 * o + 1, m + 1, hi, a); s[o] = s[2 * o] + s[2 * o + 1]; } private void push(int o, int lo, int hi) { if (lz[o] == 0) return; int m = (lo + hi) / 2; s[2 * o] += lz[o] * (m - lo + 1); lz[2 * o] += lz[o]; s[2 * o + 1] += lz[o] * (hi - m); lz[2 * o + 1] += lz[o]; lz[o] = 0; } void add(int l, int r, long v) { add(l, r, v, 1, 0, n - 1); } private void add(int l, int r, long v, int o, int lo, int hi) { if (r < lo || hi < l) return; if (l <= lo && hi <= r) { s[o] += v * (hi - lo + 1); lz[o] += v; return; } push(o, lo, hi); int m = (lo + hi) / 2; add(l, r, v, 2 * o, lo, m); add(l, r, v, 2 * o + 1, m + 1, hi); s[o] = s[2 * o] + s[2 * o + 1]; } long sum(int l, int r) { return sum(l, r, 1, 0, n - 1); } private long sum(int l, int r, int o, int lo, int hi) { if (r < lo || hi < l) return 0; if (l <= lo && hi <= r) return s[o]; push(o, lo, hi); int m = (lo + hi) / 2; return sum(l, r, 2 * o, lo, m) + sum(l, r, 2 * o + 1, m + 1, hi); } }10 Maximum subarray sum with point updates
hardEach node stores four numbers for its range: total sum, best prefix, best suffix and best subarray. Merge two children with sum = a.sum + b.sum, prefix = max(a.prefix, a.sum + b.prefix), suffix = max(b.suffix, b.sum + a.suffix), best = max(a.best, b.best, a.suffix + b.prefix). The answer is the root best, and an update rebuilds the path to the root. Time O(log n) per update, O(1) to read the answer, space O(n). Edge cases: all negative numbers (best is the largest single element, not 0), padding leaves for a power-of-two size need a neutral value, a single element.
pythonNEG = -10**18 def merge(a, b): s = a[0] + b[0] p = max(a[1], a[0] + b[1]) sf = max(b[2], b[0] + a[2]) best = max(a[3], b[3], a[2] + b[1]) return (s, p, sf, best) class MaxSub: def __init__(self, a): self.size = 1 while self.size < len(a): self.size *= 2 e = (0, NEG, NEG, NEG) self.t = [e] * (2 * self.size) for i, v in enumerate(a): self.t[self.size + i] = (v, v, v, v) for i in range(self.size - 1, 0, -1): self.t[i] = merge(self.t[2 * i], self.t[2 * i + 1]) def update(self, i, v): i += self.size self.t[i] = (v, v, v, v) while i > 1: i >>= 1 self.t[i] = merge(self.t[2 * i], self.t[2 * i + 1]) def best(self): return self.t[1][3]javaclass MaxSub { private static final long NEG = Long.MIN_VALUE / 4; private final int size; private final long[][] t; MaxSub(int[] a) { int s = 1; while (s < a.length) s *= 2; size = s; t = new long[2 * s][]; for (int i = 0; i < 2 * s; i++) t[i] = new long[]{0, NEG, NEG, NEG}; for (int i = 0; i < a.length; i++) t[s + i] = new long[]{a[i], a[i], a[i], a[i]}; for (int i = s - 1; i > 0; i--) t[i] = merge(t[2 * i], t[2 * i + 1]); } private static long[] merge(long[] a, long[] b) { return new long[]{ a[0] + b[0], Math.max(a[1], a[0] + b[1]), Math.max(b[2], b[0] + a[2]), Math.max(Math.max(a[3], b[3]), a[2] + b[1])}; } void update(int i, long v) { i += size; t[i] = new long[]{v, v, v, v}; for (i >>= 1; i >= 1; i >>= 1) t[i] = merge(t[2 * i], t[2 * i + 1]); } long best() { return t[1][3]; } }
Frequently asked questions
What is the difference between a segment tree and a Fenwick tree?
A Fenwick tree is shorter and faster for prefix sums with point updates. A segment tree handles any associative operation, range updates with lazy propagation and descents such as finding the kth element.
What is the time and space complexity of a segment tree?
Build is O(n), update and query are O(log n), and space is O(n), usually 2n for iterative or 4n for recursive layouts.
When do I need lazy propagation?
When updates apply to a whole range, such as adding a value to every element from l to r. Lazy tags postpone the work so each update still costs O(log n).
Do interviews ask segment trees?
Rarely in basic rounds, but they appear in competitive-style online assessments. The DSA coding round guide helps you decide how deep to go.
Related guides
More in DSA Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions
- String interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Topological Sort Interview Questions
- Tree DP Interview Questions
- Tree Traversal Interview Questions
- Trie (Prefix Tree) Interview Questions
- Two pointers interview questions with worked solutions
- Union-Find (Disjoint Set Union) Interview Questions
- Array interview questions with worked solutions