Autocoder

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.

BuildO(n)
Point update and range queryO(log n)
Range updateO(log n) with lazy propagation
Operation requirementAssociative 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

Segment Tree Interview Questions: questions with worked answers

  1. 1

    Range sum query with point updates (bottom-up segment tree)

    easy

    Store 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).

    python
    class 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 res
    java
    class 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. 2

    Range minimum query with updates

    easy

    The 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.

    python
    INF = 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 res
    java
    class 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. 3

    Range GCD queries with updates

    easy

    Greatest 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.

    python
    from 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 g
    java
    class 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. 4

    Kth smallest in a dynamic multiset of small integers

    medium

    Index 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.

    python
    class 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.size
    java
    class 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. 5

    First index at or after a position whose value is at least x

    medium

    Store 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.

    python
    class 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)
    java
    class 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. 6

    Count inversions using a segment tree

    medium

    An 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.

    python
    def 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 inv
    java
    long 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. 7

    Count of smaller numbers after self

    medium

    For 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.

    python
    def 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 res
    java
    List<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. 8

    Longest increasing subsequence using a max segment tree

    medium

    Process 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.

    python
    def 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 best
    java
    int 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. 9

    Range add and range sum with lazy propagation

    hard

    A 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.

    python
    class 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)
    java
    class 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. 10

    Maximum subarray sum with point updates

    hard

    Each 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.

    python
    NEG = -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]
    java
    class 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

See all in this section