AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Segment Tree coding problems

A segment tree splits an array into halves, quarters and so on down to single elements, and stores an aggregate — a sum, a minimum, a bitwise OR — for every piece.

12 problems · 4 medium · 8 hard · judged by hidden tests in 13 languages

12problems

0 easy

4 medium

8 hard

Sign in to tick off what you solve.

Study plan: 7 problems · about 5 h 5 min

Start the study plan

Next up: Range Sum Query - Mutable

How it works

Segment Tree, step by step

Range sum queries, with a segment tree

a = [2, 5, 1, 4, 3, 6]; sum(1, 4)

[0,0][1,1][0,1][2,2][0,2][3,3][4,4][3,4][5,5][3,5][0,5]a205112433465each node: sum of its range

A segment tree cuts the array in half again and again: the root covers a[0..5], each node's range is split at its middle between two children, and a leaf is a single index. Every node will hold the sum of its range.

0:01 / 0:33Step 1 of 10
Transcript · 10 steps

Study plan

Learn segment tree in 6 days

7 of the 12 Segment Tree problems (4 medium and 3 hard) over 6 days, about 5 h 5 min in all — the pattern first, then easiest to hardest. After that, the other 5 in the full list below are practice at your own pace. Then move on to Binary Indexed Tree.

  1. Day 1

    about 50 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

  2. Day 2

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  3. Day 3

    about 35 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  5. Day 5

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  6. Day 6

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Binary Indexed Tree

Segment Tree Coding Problems: 12 Questions with Solutions

12 segment tree coding problems — 4 medium · 8 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 6-day plan.

  • Problems: 12
  • By difficulty: 4 medium · 8 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A segment tree splits an array into halves, quarters and so on down to single elements, and stores an aggregate — a sum, a minimum, a bitwise OR — for every piece. Any range is covered by a logarithmic number of stored pieces, so a range query and a single-element update both take O(log n) time, where a plain array makes one of them linear. It works for any operation that combines two neighbouring answers into one. The problems here practise building the tree, querying a range, and indexing it by value to count what has been inserted so far.

How segment tree works, step by step

2[0,0]5[1,1]7[0,1]1[2,2]8[0,2]4[3,3]3[4,4]7[3,4]6[5,5]13[3,5]21[0,5]a205112433465query [1,4]sum = 5 + 1 + 7 = 13
Range sum queries, with a segment tree. Example: a = [2, 5, 1, 4, 3, 6]; sum(1, 4)
  1. A segment tree cuts the array in half again and again: the root covers a[0..5], each node's range is split at its middle between two children, and a leaf is a single index. Every node will hold the sum of its range.
  2. The leaves copy the array: leaf [i,i] holds a[i]. Each node above will be the sum of its two children, so the tree fills from the bottom up and never rereads the array.
  3. One level up, each node adds its two children: [0,1] = 2 + 5 = 7 and [3,4] = 4 + 3 = 7.
  4. Another level up, the same rule again: [0,2] = 7 + 1 = 8 and [3,5] = 7 + 6 = 13.
  5. The root is 8 + 13 = 21, the sum of the whole array. Building touched each of the 11 nodes once, so it is O(n).
  6. Query sum(1, 4). The root's range [0,5] only partly overlaps [1,4], so its 21 cannot be used as it is, and the query asks both children.
  7. Depth 1: [0,2] and [3,5] only partly overlap, so the query goes into their children.
  8. Depth 2: [2,2] (1) and [3,4] (7) lie inside [1,4], so their sums are taken whole, and nothing below is visited; [0,1] only partly overlaps, so the query goes into its children; [5,5] is outside the range and skipped.
  9. Depth 3: [1,1] (5) lies inside [1,4], so its sum is taken whole; [0,0] is outside the range and skipped.
  10. sum(1, 4) = 5 + 1 + 7 = 13, from 3 nodes. At each depth at most two nodes straddle an end of the range, so a query visits O(log n) nodes, and an update changes one leaf and its O(log n) ancestors.

Segment Tree study plan

7 of the 12 Segment Tree problems (4 medium and 3 hard) over 6 days, about 5 h 5 min in all — the pattern first, then easiest to hardest. After that, the other 5 in the full list below are practice at your own pace. Then move on to Binary Indexed Tree.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 5

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 6

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Binary Indexed Tree

Segment Tree: the essentials

When to reach for it

An array that changes while range questions arrive: the sum, minimum or OR of nums[l..r] between updates, 10⁵ of each. Prefix sums answer a range in O(1) but take O(n) per update; a segment tree does both in O(log n). Indexed by value, it counts the inserted values below x. For prefix sums alone, a Binary Indexed Tree is shorter.

The pattern

Iteratively, the values sit at tree[n:] and node i combines children 2i and 2i + 1. An update changes a leaf and every ancestor: a sum adds the delta, a minimum or OR recomputes each from its two children. A query on [l, r) climbs from both ends; at an odd end, the node just inside lies in the range but its parent does not, so it is added alone.

def add(tree, n, i, delta):             # nums[i] += delta; nums[i] is tree[n + i]
    i += n
    while i:
        tree[i] += delta                # the leaf, then every ancestor
        i //= 2

def range_sum(tree, n, l, r):           # sum of nums[l:r]
    total, l, r = 0, l + n, r + n
    while l < r:
        total += (tree[l] if l % 2 else 0) + (tree[r - 1] if r % 2 else 0)
        l, r = (l + 1) // 2, r // 2
    return total

Cost

O(log n) per update and per query, in 2n cells. Building is O(n): fill the leaves, then each node from its children, n - 1 down to 1. The recursive form extends to range updates (lazy propagation) but needs up to 4n cells.

Common mistakes

  • Sizing a recursive tree at 2n cells: unless n is a power of two it needs up to 4n.
  • Mixing half-open [l, r) and closed [l, r] ranges.
  • Storing something two halves cannot be combined into, such as a count of distinct values.
  • Indexing by value when values reach 10⁹; compress them to ranks first.

Start with

All segment tree problems

Medium (4)

Hard (8)

Companies that ask segment tree problems

  • Amazon 10 problems on segment tree
  • Google 10 problems on segment tree
  • Meta 2 problems on segment tree
  • Uber 2 problems on segment tree
  • Microsoft 1 problem on segment tree

Next topic: Binary Indexed Tree