DSA · Advanced structures

Answer a range query without reading the range

Q: What is a segment tree?

A binary tree where every node stores the answer for one contiguous slice of the array — the root covers the whole array, every leaf covers one element, and every internal node covers its two children joined. It answers a range query and a point update in O(log n) each. The combine has to be associative, so sum, min, max, gcd and xor all work.

Q: How many nodes does a range query actually touch, and why is that O(log n)?

At most about four per level, so roughly 4·log₂n in total — on an array of 100,000 that is never more than about 70 nodes. The reason for the cap: at each level at most two nodes straddle the edges of the range, one at each end, and every other node at that level is settled by "completely outside" or "completely inside" without descending. Since there are log₂ n levels, the total is logarithmic. In the 8-leaf tree from the lesson, sum(2..6) visits 9 of the 15 nodes and skips 6.

Q: Why do you allocate 4n and not 2n?

With the recursive 2v / 2v+1 indexing and an n that is not a power of two, the tree is not perfect and the largest index used can approach 4n. 2n is only safe when n is a power of two — which is why an 8-element example hides the bug. The iterative bottom-up segment tree needs exactly 2n , and that is one of the main reasons people prefer it.

Q: Prefix sums answer a range sum in O(1). Why would anyone build a tree?

Because one point update invalidates every prefix after it, so the update is O(n) . With u updates and q queries prefix sums cost O(u·n + q) while the tree costs O((u+q) log n) . If the array is static, prefix sums are the right answer and a tree is a waste of interview time.

Q: Segment tree or Fenwick tree?

Fenwick when you only need prefix sums, and therefore range sums by subtraction, with point updates: same O(log n) , a quarter of the code, better constant. Segment tree when the operation has no inverse — min, max, gcd — because you cannot recover a range answer by subtracting two prefixes. Also segment tree when you need range updates, since that is where lazy propagation lives.

Q: How does a point update work, and why is it O(log n)?

Walk from the root down to the leaf that owns the index, write the leaf, then recompute each node on the way back up from its two children. Only nodes on that single root-to-leaf path contain the index, so nothing else can change. Setting a[3] to 5 in the lesson tree rewrites exactly four nodes — 11, 5, 2 and 1 — and the path length is the depth, log₂ n .

Q: What is lazy propagation, in one sentence?

It is what makes a range update O(log n) instead of O(n) : rather than pushing "add 3 to everything in this range" down to every leaf, you stop at the same handful of covering nodes a query would use, park the pending 3 there, and push it to the children only when a later query actually needs to descend past them.

Q: Why does KMP never move the text pointer backwards?

Because the LPS array already encodes what the recent text characters were: they are a prefix of the pattern. On a mismatch you slide the pattern forward by j − lps[j−1] and resume at the same text index, so nothing already verified is compared twice. The text pointer only advances, which gives O(n) for the search and O(n+m) overall.

Q: On a mismatch, why lps[j−1] and not lps[j]?

j is the position that just failed, so pattern[j] was never verified against the text. The part that did match is pattern[0..j−1] , and lps[j−1] is the longest pattern prefix that is also a suffix of exactly that verified part. Using lps[j] assumes a character the text does not have and silently skips real matches.

A prefix-sum array answers any range sum in one subtraction — until someone changes a value and you rebuild all of it. A segment tree keeps the query and the update at O(log n). Build one over eight numbers here, watch a query light 9 of its 15 nodes, then meet the Fenwick tree and KMP.

Build the tree, then run a query on it →

15 nodes8 leaves + 7 internal · built with 7 additions

→

9 visitedsum(2..6) touches these · 6 subtree nodes never read

→

3 carry it8 + 12 + 6 = 26

01 The idea

Precompute the halves, not the answers

You have an array and two kinds of request: "what is the sum of positions 2 to 6" and "position 3 just became 5". Handle them with a plain array and the query costs O(n) while the update costs O(1). Precompute prefix sums and you flip it — the query drops to O(1), but one changed value invalidates every prefix after it, so the update climbs to O(n). Either way, a workload that mixes the two costs you n per operation somewhere.

A segment tree refuses both extremes. It stores the answer for the whole array, for each half, for each quarter, and so on down to single elements. Any range you are asked about is a handful of those stored pieces glued together, and any single change touches only the pieces that contain it — one path from a leaf to the root. Both operations land at O(log n), and that symmetry is the entire reason the structure exists.

Store the answer for every half, quarter and eighth of the array. Any range you are asked about is a few of those pieces added together, and any one change only disturbs the pieces directly above it.

Segment treeA binary tree where every node holds the answer for one contiguous slice of the array. The root covers everything, each leaf covers one element, and each internal node covers exactly its two children joined.

Associative combineThe operation that merges two children into a parent. Sum, min, max, gcd and xor all work, because regrouping does not change the result. Average does not work — you cannot average two averages.

LPS arrayFor a pattern, lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. KMP reads it to decide where to restart after a mismatch.

02 Worked example

Eight numbers, fifteen nodes, one query

The array is 5 2 7 1 9 3 6 4, and every number quoted below comes from it — right up to the update section further down, which deliberately changes a[3] so you can watch the repair. Build it first. Leaves hold the eight values; every level above adds pairs. Each row below prints a node's stored value once for every array position that node covers, so the spans line up as a pyramid — the tree stores each number once, not eight times.

index01234567

leaves52719364nodes 8..15 · one cell each

level 2778812121010nodes 4..7 · pairs

level 11515151522222222nodes 2, 3 · halves

root3737373737373737node 1 · whole array = 37

Node numbering is the trick that makes the code short: the root is node 1, and node v has children 2v and 2v+1. So node 2 covers 0..3, node 5 covers 2..3, node 14 covers position 6 alone. Now ask for sum(2..6), which is 7 + 1 + 9 + 3 + 6 = 26. The query starts at the root and asks one question of every node it reaches: is your slice completely outside my range, completely inside it, or straddling the edge?

n1 · 0..73737373737373737straddles · split

n2 · 0..315151515····straddles · split

n4 · 0..177······outside · return 0

n5 · 2..3··88····inside · take 8

n3 · 4..7····22222222straddles · split

n6 · 4..5····1212··inside · take 12

n7 · 6..7······1010straddles · split

n14 · 6..6······6·inside · take 6

n15 · 7..7·······4outside · return 0

result··8812126·8 + 12 + 6 = 26

Count what the query never looked at. Node 4 said "outside" and its two leaves, 8 and 9, were never visited. Node 5 said "inside" and its two leaves, 10 and 11, were never visited either — the answer was already sitting in the parent. Node 6 cut two more the same way. That is 6 of the 15 nodes skipped, 9 visited, and only 3 of those nine actually contributed a number.

Be honest about the scoreboard at this size: a plain scan reads 5 cells, and the tree visited 9 nodes. At n = 8 the tree loses. What it buys is the growth rate — the visited count is bounded by about four nodes per level, and levels grow like log n. On 100,000 values no range query visits more than about 70 nodes, while the scan reads up to 100,000.

03 The code

Prefix sums, a tree, and two more tools

Put the two structures side by side on the same array. The prefix version wins the query outright and loses the update outright. The tree gives up O(1) queries to buy a cheap update, and everything else in this module is a variation on that bargain.

Prefix sums — O(1) query, O(n) update

pre[0] = 0for i in 0..n−1:    pre[i+1] = pre[i] + a[i]   # O(n) oncesum(l, r) = pre[r+1] − pre[l]  # 33 − 7 = 26set a[3]=5: for j in 4..n: pre[j] += 4

Segment tree — O(log n) query, O(log n) update

query(v, lo, hi, l, r):    if r < lo or hi < l:     return 0   # outside    if l <= lo and hi <= r:  return t[v] # inside    mid = (lo + hi) / 2    return query(2v,   lo,      mid, l, r)         + query(2v+1, mid + 1, hi,  l, r)

Why two base cases and not one? They do different jobs and neither is optional. Line 2 is what abandons a whole subtree — it is why nodes 8 and 9 were never read. Line 3 is what stops the descent early — it is why nodes 10 and 11 were never read even though they are inside the range. Delete line 3 and the recursion walks every leaf in the range: O(n), exactly the scan you were trying to avoid. Delete line 2 and this code does not merely get slow — a leaf outside the range fails line 3, computes mid = lo = hi, and recurses into itself forever.

Why does the query stay O(log n)? At any level of the tree, at most two nodes straddle the range — one at each end of it. Every other node at that level is settled by line 2 or line 3 without descending. So the visited count is capped at roughly four nodes per level, and there are log₂ n levels. On our 8-leaf tree that ceiling is loose: 9 visited against a 5-cell scan. At n = 100,000 it is under 70 against 100,000.

Why not just rebuild the prefix array after each update? One update is O(n). Interleave 100,000 updates with 100,000 queries and the prefix version does about 10¹⁰ operations, which is minutes. The tree does about 200,000 × 17 ≈ 3.4 million, which is milliseconds. The break-even is not close.

The point update, and why only one path changes

update(v, lo, hi, i, val):    if lo == hi: t[v] = val; return        # the leaf    mid = (lo + hi) / 2    if i <= mid: update(2v,   lo,      mid, i, val)    else:        update(2v+1, mid + 1, hi,  i, val)    t[v] = t[2v] + t[2v+1]                  # repair going back up

Trace it on our array. Set a[3] from 1 to 5. The walk is 1 → 2 → 5 → 11. The root's mid is 3, and line 4's i <= mid test sends index 3 to the left child; node 2's mid is 1, so it goes right; node 5's mid is 2, so it goes right again. Write the leaf, then repair on the way out: node 11 becomes 5, node 5 goes 8 → 12, node 2 goes 15 → 19, the root goes 37 → 41. Four writes. Every other node is untouched, because no other node's slice contains index 3. The prefix-sum version rewrites pre[4..8] — five cells here, and n − i cells for an update at index i.

Fenwick tree — the same job in six lines

A Fenwick tree, also called a binary indexed tree or BIT, does prefix sums with point updates and nothing else. Same O(log n) on both, a quarter of the code, and a noticeably better constant. It is 1-indexed, and index i owns the block of values ending at i whose length is i's lowest set bit, which i & (−i) extracts.

add(i, delta):                # 1-indexed, i = 1..n    while i <= n:  bit[i] += delta;  i += i & (−i)prefix(i):                    # sum of a[1..i]    s = 0    while i > 0:   s += bit[i];      i −= i & (−i)    return s   # range: prefix(r) − prefix(l−1)

The same query, the same answer. Written 1-indexed our array is a[1..8] = 5 2 7 1 9 3 6 4, so the 0-indexed range 2..6 is 1-indexed 3..7 and sum(2..6) becomes prefix(7) − prefix(2). The tree holds bit = 5 7 7 15 9 12 6 37. prefix(7) walks 7 → 6 → 4 and adds 6 + 12 + 15 = 33; prefix(2) is just 7. That is 26 again. Look at the three blocks it used: 6, 12 and 15 are segment-tree nodes 14, 6 and 2. A Fenwick tree keeps the subset of segment-tree nodes that prefix sums need and throws the rest away — which is also why it cannot answer a range minimum. There is no "subtract one prefix from another" for a minimum.

KMP — never re-read a text character

Naive substring search restarts the pattern at every text position, so a text of length n and a pattern of length m cost O(n·m) in the worst case — searching for aaab inside a million as hits that ceiling exactly. KMP spends O(m) up front building the LPS array, then walks the text once and never moves the text pointer backwards.

i	pattern[0..i]	longest proper prefix that is also a suffix	lps[i]
0	a	a single character has no proper prefix	`0`
1	ab	prefix a vs suffix b — no match	`0`
2	aba	a	`1`
3	abab	ab	`2`
4	ababc	nothing ends in c except the whole string	`0`

On a mismatch at pattern position j, set j = lps[j−1] and compare again at the same text position. Only when j is already 0 do you move the text pointer forward.

Search ababc inside abababc. Positions 0 to 3 match, so j reaches 4. At text index 4 the text has a and the pattern wants c — mismatch. Instead of restarting, set j = lps[3] = 2: the last two matched characters were ab, which is already a prefix of the pattern, so those two comparisons are never repeated. Text index 4 then matches, and so do 5 and 6, giving a hit starting at index 2. Eight character comparisons in total, against eleven for the naive scan on this tiny input — and O(n) against O(n·m) as the strings grow.

Two names to recognise, not to learn today. Matrix exponentiation raises a linear recurrence's k×k transition matrix to the n-th power by repeated squaring, giving O(k³ log n) — that is how you get the 10¹⁸-th Fibonacci number modulo a prime. Mo's algorithm sorts offline range queries into √n blocks so one pair of pointers sweeps the array, answering q queries in O((n + q)√n) when there are no updates. If a problem statement smells like either, knowing the name is most of the battle.

05 Cheat sheet

Costs worth memorising

Structure	Build	Range query	Point update	Space
Plain array	`O(1)`	`O(n)`	`O(1)`	`n`
Prefix-sum array	`O(n)`	`O(1)`	`O(n)`	`n`
Fenwick tree (BIT)	`O(n log n)`	`O(log n)`	`O(log n)`	`n`
Segment tree	`O(n)`	`O(log n)`	`O(log n)`	`4n`
Segment tree + lazy	`O(n)`	`O(log n)`	`O(log n)` per range update	`8n`

Substring search	Preprocess	Search	Extra memory
Naive restart at every position	`—`	`O(n·m)`	`O(1)`
KMP with the LPS array	`O(m)`	`O(n)`	`O(m)`

Allocate 4n, not 2nWith recursive 2v / 2v+1 indexing and an n that is not a power of two, the largest index used can approach 4n. Our n = 8 fits in 15 slots and hides the problem; a real n will not.

Fenwick is 1-indexedi & (−i) is 0 when i is 0, so a 0-indexed Fenwick loops forever inside add and returns 0 from prefix. Shift every index by one on the way in and out.

lps[j−1], never lps[j]On a mismatch at pattern position j, only pattern[0..j−1] was ever verified, so the fallback has to be the LPS of that. Reading lps[j] trusts a character the text does not have.

06 Where & why

Rarely needed, and decisive when they are

Say the honest thing first: across a whole placement season you may meet one segment-tree problem and no KMP at all. The bulk of every round is arrays, strings, hashing, two pointers, stacks and plain trees. What makes this module worth an evening is that these problems carry no partial credit — you either notice that the updates make prefix sums illegal, or you do not solve it.

Reach for it when…

Updates and range queries interleaveThat mix is the whole trigger. A static array wants prefix sums; an array you never range-query wants nothing at all. Only the mixture forces O(log n) on both sides.

The combine is associative and has an identitySum with 0, min with +infinity, max with −infinity, gcd with 0, xor with 0. Without an identity you have no value to return for the outside case.

The strings are repetitive or adversarialNaive search is fine on English prose. It degrades to O(n·m) on DNA, binary strings, or long runs of one character — which is exactly what a setter chooses.

The round is an online, CP-style contestThe elite online rounds and ICPC-style sets do post problems whose intended solution is a segment tree. Standard product-company DSA interviews almost never do.

Use something else when…

Situation	Better choice	Why
The array never changes	Prefix-sum array	`O(1)` per query, one pass to build, four lines. A tree here is showing off and costs you time on the clock.
You only need prefix sums with point updates	Fenwick tree	Same `O(log n)` both ways, a quarter of the code, better constant. Fewer places to make an off-by-one.
Range minimum on a static array	Sparse table	`O(n log n)` to build, then `O(1)` per query. It beats the tree precisely because there are no updates to survive.
All queries known up front, no updates	Mo's algorithm	`O((n+q)√n)` offline, and it handles answers a tree cannot merge — "how many distinct values in this range" has no combine.
You just need to find a substring in real code	The library's find	str.find, indexOf and memmem are already tuned and vectorised. Hand-written KMP is usually slower and always riskier.

Learn the shape of the problem before the code. "Point updates mixed with range queries" should make you reach for a tree the way "sorted array, find a boundary" makes you reach for binary search. In an interview, saying that sentence out loud earns more than typing the 30 lines — the recognition is what is being tested.

07 Interview questions

What interviewers actually ask

Eleven questions in the order a round escalates: what the structure is, how fast, why that fast, the sibling comparison, and the honest one at the end.

What is a segment tree?

A binary tree where every node stores the answer for one contiguous slice of the array — the root covers the whole array, every leaf covers one element, and every internal node covers its two children joined. It answers a range query and a point update in O(log n) each. The combine has to be associative, so sum, min, max, gcd and xor all work.

How many nodes does a range query actually touch, and why is that O(log n)?

At most about four per level, so roughly 4·log₂n in total — on an array of 100,000 that is never more than about 70 nodes. The reason for the cap: at each level at most two nodes straddle the edges of the range, one at each end, and every other node at that level is settled by "completely outside" or "completely inside" without descending. Since there are log₂ n levels, the total is logarithmic. In the 8-leaf tree from the lesson, sum(2..6) visits 9 of the 15 nodes and skips 6.

Why do you allocate 4n and not 2n?

With the recursive 2v / 2v+1 indexing and an n that is not a power of two, the tree is not perfect and the largest index used can approach 4n. 2n is only safe when n is a power of two — which is why an 8-element example hides the bug. The iterative bottom-up segment tree needs exactly 2n, and that is one of the main reasons people prefer it.

Prefix sums answer a range sum in O(1). Why would anyone build a tree?

Because one point update invalidates every prefix after it, so the update is O(n). With u updates and q queries prefix sums cost O(u·n + q) while the tree costs O((u+q) log n). If the array is static, prefix sums are the right answer and a tree is a waste of interview time.

Segment tree or Fenwick tree?

Fenwick when you only need prefix sums, and therefore range sums by subtraction, with point updates: same O(log n), a quarter of the code, better constant. Segment tree when the operation has no inverse — min, max, gcd — because you cannot recover a range answer by subtracting two prefixes. Also segment tree when you need range updates, since that is where lazy propagation lives.

How does a point update work, and why is it O(log n)?

Walk from the root down to the leaf that owns the index, write the leaf, then recompute each node on the way back up from its two children. Only nodes on that single root-to-leaf path contain the index, so nothing else can change. Setting a[3] to 5 in the lesson tree rewrites exactly four nodes — 11, 5, 2 and 1 — and the path length is the depth, log₂ n.

What is lazy propagation, in one sentence?

It is what makes a range update O(log n) instead of O(n): rather than pushing "add 3 to everything in this range" down to every leaf, you stop at the same handful of covering nodes a query would use, park the pending 3 there, and push it to the children only when a later query actually needs to descend past them.

What is the LPS array, and what does KMP do with it?

For a pattern, lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it — for ababc it is 0 0 1 2 0. KMP consults it the moment a comparison fails, to work out how far the pattern can slide without discarding anything already verified. It costs O(m) time to build and O(m) memory, and it is the only extra state KMP carries.

Why does KMP never move the text pointer backwards?

Because the LPS array already encodes what the recent text characters were: they are a prefix of the pattern. On a mismatch you slide the pattern forward by j − lps[j−1] and resume at the same text index, so nothing already verified is compared twice. The text pointer only advances, which gives O(n) for the search and O(n+m) overall.

On a mismatch, why lps[j−1] and not lps[j]?

Hard

Given an array of n ≤ 100,000 integers, each between 1 and 100,000, return the number of pairs (i, j) with i < j and a[i] > a[j].

Follow-up

There is no range query anywhere in the statement — you have to invent one, and the array you invent it over is not the input array. The four-line double loop is O(n²) and dies at n = 100,000; every hard decision here is about what to index and what to count.

Show the hint

Sweep left to right and, for each new element, ask how many of the elements already behind you are strictly greater than it. That is a counting question about values, not positions — so let the Fenwick index be the value, and let each cell hold how many times that value has appeared.