Segment Tree Coding Problems: 2 Questions with Solutions

How segment tree works, step by step

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

All 2 Segment Tree problems (2 hard) over 2 days, about 1 h 55 min in all — the pattern first, then easiest to hardest. 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.

• Create Sorted Array Through Instructions Hard

Day 2

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

• Find Subarray With Bitwise OR Closest to K Hard

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

• Create Sorted Array Through Instructions: counts indexed by value, two range sums per insertion.
• Find Subarray With Bitwise OR Closest to K: a range OR, binary searched from each left end.

All segment tree problems

Hard (2)

• Create Sorted Array Through Instructions Array, Binary Search, Divide and Conquer
• Find Subarray With Bitwise OR Closest to K Bit Manipulation, Array, Binary Search

Companies that ask segment tree problems

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

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems