Segment Tree Problems
A segment tree is a binary tree over an array where each node stores the answer (sum, min, GCD…) for one range, so range queries and updates both run in O(log n).
20 problems from LightOJ, SPOJ and Codeforces, ordered from first segment tree to hard. Each one is tagged with the technique it teaches and links to my solution. Tick off the ones you solve; your progress is saved in this browser.
-
1
Find the minimum value in a range [l, r].
-
2
Support 2 operations:
- Invert every bit in [i, j]
- Report whether the i-th bit is 0 or 1
-
3
Support 3 operations:
- Report a[id], then set it to zero
- Add v to a[id]
- Sum of [l, r]
-
4
Support 2 operations:
- Add v to every number in [l, r]
- Sum of [l, r]
-
5
Support 2 operations:
- Assign ap = b
- Print v, obtained by alternately OR-ing and XOR-ing adjacent pairs up the tree
-
6
Animals are present during time intervals. For each query [L, R] (the hunter's time in the forest), find the most animals a single shot at any moment in [L, R] can hit.
-
7
Query(x, y) = max { a[i] + … + a[j] : x ≤ i ≤ j ≤ y }.
-
8
Support 2 operations:
- Set the i-th element to v
- Query(x, y) = max { a[i] + … + a[j] : x ≤ i ≤ j ≤ y }
-
9
Support 2 operations:
- Set A[i] = x
- Find i ≠ j in [x, y] maximising A[i] + A[j]
-
10
Posters are glued in order, the i-th covering sections [li, ri]. Count the posters that are still at least partly visible.
-
11
Support 2 operations:
- Flip the i-th bracket
- Check whether the whole word is a correct bracket sequence
-
12
Support 2 operations:
- Toggle every switch in [l, r]
- Count lights that are on in [l, r]
-
13
Support 2 operations:
- Set every number in [x, y] to v
- Count primes in [x, y]
-
14
For each query [l, r], find the length of the longest correct bracket subsequence of s[l..r].
-
15
Support 2 operations:
- Add 1 to every number in [A, B]
- Count numbers in [A, B] divisible by 3
-
16
Query(x1, y1, x2, y2) = max { A[i] + … + A[j] : x1 ≤ i ≤ y1, x2 ≤ j ≤ y2 }, with x1 ≤ x2 and y1 ≤ y2. The two ranges may overlap.
-
17
Support 2 operations:
- XOR every element in [l, r] with x
- Sum of [l, r]
-
18
For each query (i, j, k), count the elements of ai, …, aj greater than k. Queries are encoded, so they must be answered online.
-
19
In [l, r] every pair of ants fights; ant i scores a point when si divides sj. Ants with exactly r − l points are freed. Count how many ants get eaten.
-
20
An Nx × Ny × Nz box of unit cubes. Toggle whole slabs along the X, Y or Z axis, then count red cubes inside a cuboid (x1, y1, z1)–(x2, y2, z2).
No problems match. Clear filters
Frequently asked questions
What is a segment tree?
A segment tree is a binary tree built over an array where each node stores an aggregate (sum, minimum, GCD, and so on) of a contiguous range. It answers range queries and applies point updates in O(log n) time, using O(n) memory.
What is lazy propagation in a segment tree?
Lazy propagation defers range updates: instead of updating every element in [l, r], you tag the O(log n) nodes that cover the range and push the pending update down to children only when a later query or update visits them. This keeps range updates at O(log n).
In what order should I solve these segment tree problems?
Top to bottom. The list starts with plain range-minimum and range-sum queries, moves to lazy propagation, then to nodes that store custom merged state (such as the GSS maximum-subarray series), and ends with harder combinations like inclusion–exclusion over 3D toggles.