Advanced Trees

Why Go Beyond a Plain BST?

In Binary Trees & BST every operation cost O(h), where h is the height. That is a promise about the shape, and the shape depends on the order in which keys arrive. Sorted input, which is very common in real data, turns the tree into a linked list. The demo 59_avl_tree.go inserts the keys 1 to 2000 in increasing order into both kinds of tree:

A search in the plain tree walks 2,000 nodes; in the AVL tree, at most 11. The rest of the lesson is about two other problems a plain BST cannot solve even when it is balanced: questions about prefixes of keys, and questions about ranges of positions.

The Toolbox

Go's standard library has hash maps, slices and heaps, but no ordered map or balanced tree, so these structures are ones you write yourself, or take from a library. Knowing how they work also tells you which one a problem is really asking for.

AVL Trees: Balance by Rotation

An AVL tree is a binary search tree that obeys one extra rule: for every node, the heights of the two subtrees differ by at most 1. After every insert or delete, the nodes on the path back to the root are checked and repaired if the rule broke. The rule looks weak, but it is enough to bound the height.

Why the Rule Gives O(log n)

Ask the opposite question: what is the fewest nodes an AVL tree of height h can have? The root needs one subtree of height h-1 and, at least, one of height h-2. So the smallest tree is:

func minNodes(h int) int {
	if h <= 0 {
		return 0
	}
	if h == 1 {
		return 1
	}
	return minNodes(h-1) + minNodes(h-2) + 1
}

This grows like the Fibonacci numbers: 12 nodes for height 5, 143 for height 10, 17,710 for height 20, 2,178,308 for height 30. Turned around, a tree with n nodes has height at most about 1.44 log₂(n+2). A million keys need height at most 28, where a perfectly balanced tree would need 20. The demo tests this after random operations: no AVL tree ever has fewer nodes than minNodes of its height.

The Node

Each node stores its own height, so the balance of a node is read in O(1) from its children:

type node struct {
	key         int
	height      int // height of the subtree rooted here: a leaf is 1, nil is 0
	left, right *node
}

func fix(n *node) { n.height = 1 + max(height(n.left), height(n.right)) }

fix recomputes one height from the two children. Any function that changes a child pointer must call it before returning, always bottom-up. Forgetting one call leaves a stale height, and the balance decisions above it will be wrong.

The Rotation

A rotation is a local pointer change that lifts one node above its parent. It keeps the in-order sequence of keys, so the search-tree property survives, but it moves one subtree up a level and another one down:

A single rotation fixes a straight chain. A zig-zag needs two.

func rotateRight(y *node) *node {
	x := y.left
	y.left = x.right
	x.right = y
	fix(y) // y is now the lower node, so it is updated first
	fix(x)
	rotations++
	return x
}

The subtree that changes parent (x.right, called B in the demo's diagram) holds keys larger than x and smaller than y, so it fits exactly as y's new left child. The function returns the new root of this subtree, and the caller must store it. rotateLeft is the mirror image.

The Four Cases

After one insert or delete, a node can only be off by two, and only four shapes exist. Two are straight (left-left, right-right) and need one rotation. Two are zig-zags (left-right, right-left): the child leans away from the parent, so a single rotation would only move the problem to the other side. Rotate the child first to straighten the zig-zag, then rotate the parent.

func rebalance(n *node) *node {
	fix(n)
	switch b := balance(n); {
	case b > 1:
		if balance(n.left) < 0 {
			n.left = rotateLeft(n.left) // left-right case
		}
		return rotateRight(n)
	case b < -1:
		if balance(n.right) > 0 {
			n.right = rotateRight(n.right) // right-left case
		}
		return rotateLeft(n)
	}
	return n
}

The demo inserts the same three keys in four orders. Every order ends as the tree with root 20: the two straight orders use one rotation, the two zig-zag orders use two.

insert order   shape         rotations   preorder after inserts
[30 20 10]     left-left     1           20 10 30
[10 20 30]     right-right   1           20 10 30
[30 10 20]     left-right    2           20 10 30
[10 30 20]     right-left    2           20 10 30

Insert and Delete

Insert is the plain BST insert with one change: on the way back up the recursion, each node calls rebalance instead of returning itself.

	switch {
	case k < n.key:
		n.left = insert(n.left, k, added)
	case k > n.key:
		n.right = insert(n.right, k, added)
	default:
		return n // already present: nothing changed, nothing to rebalance
	}
	return rebalance(n)

Delete works the same way. A node with two children takes the key of its in-order successor, which is then removed from the right subtree. Unlike insert, one delete can unbalance several nodes on the path, so every node on the way up is rebalanced. An insert needs at most two rotations in total; a delete may need one per level.

What the Demo Measures

• Sorted inserts. 2,000 keys use 1,989 rotations and reach height 11, the minimum possible for 2,000 nodes. Deleting the 1,900 smallest keys afterwards leaves a valid tree of height 7.
• Random order. Over 200 random orders of 1,000 keys the tallest plain tree has height 29 and the tallest AVL tree height 12, under the bound of 14. Balancing helps a little on random input and enormously on sorted input.
• Oracle. 20,000 random inserts, deletes and lookups are applied to the tree and to a Go map. After every single operation a check function verifies the search order, the stored heights and the balance rule for the whole tree. Failures: 0.

Treaps and Order Statistics

AVL trees need four cases and careful height bookkeeping. A treap gets the same guarantee, in expectation, from one idea: give every node a random priority, and keep the tree a BST by key and a heap by priority (a parent's priority is at least its children's). For a given set of keys and distinct priorities exactly one such tree exists, and because the priorities are random, its shape is the shape of a randomly built BST. Sorted input no longer matters. The demo is 60_treap_order_statistics.go.

Split and Merge

Instead of rotations, a treap is built from two operations that each follow a single path:

• split(n, k) cuts a tree into the keys smaller than k and the keys at least k.
• merge(a, b) joins two trees when every key of a is below every key of b. The node with the higher priority becomes the root.

func split(n *node, k int) (*node, *node) {
	if n == nil {
		return nil, nil
	}
	if n.key < k {
		l, r := split(n.right, k) // n and its left subtree belong to the left part
		n.right = l
		update(n)
		return n, r
	}
	l, r := split(n.left, k) // n and its right subtree belong to the right part
	n.left = r
	update(n)
	return l, n
}

func merge(a, b *node) *node {
	switch {
	case a == nil:
		return b
	case b == nil:
		return a
	case a.prio > b.prio:
		a.right = merge(a.right, b)
		update(a)
		return a
	default:
		b.left = merge(a, b.left)
		update(b)
		return b
	}
}

Insert and erase are then a few lines. To insert, split at the key and merge the new node between the two halves. To erase, split at k and again at k+1: the middle tree holds only the key k, and the other two are merged without it.

	l, r := split(t.root, k)
	fresh := &node{key: k, prio: t.rng.Uint32(), size: 1}
	t.root = merge(merge(l, fresh), r)

Augmenting: Store the Size

Each node also stores size, the number of nodes in its subtree, repaired by update whenever a child pointer changes. Nothing else about the tree changes, yet it can now answer questions a plain BST cannot, in O(log n). This technique is called augmentation: keep one more number per node that can be recomputed from the children, and use it to steer a search.

func (t *Treap) Kth(i int) (int, bool) {
	if i < 0 || i >= t.Len() {
		return 0, false
	}
	n := t.root
	for {
		ls := size(n.left)
		switch {
		case i < ls:
			n = n.left
		case i == ls:
			return n.key, true
		default:
			i -= ls + 1
			n = n.right
		}
	}
}

The size of the left subtree says where the i-th smallest key is: on the left if the left has more than i nodes, here if it has exactly i, and otherwise on the right, after skipping the left subtree and this node. Rank is the same idea in reverse: while walking to k, every time you step right, everything to the left of that step (the left subtree plus the node) is smaller.

func (t *Treap) Rank(k int) int {
	count := 0
	for n := t.root; n != nil; {
		if k <= n.key {
			n = n.left
		} else {
			count += size(n.left) + 1 // this node and its whole left subtree are smaller
			n = n.right
		}
	}
	return count
}

Count(lo, hi), the number of keys in a range, is Rank(hi+1) - Rank(lo). Together these give the median, percentiles, and "how many values are below x" for a set that keeps changing, something a sorted slice can only do by paying O(n) for each insert.

What the Demo Measures

• Balance without rules. 100,000 keys inserted in sorted order give a tree of height 44 with an average depth of 22, against log₂ n = 16.6. A plain BST would have height 100,000.
• Oracle. 30,000 random insert, erase, k-th, rank and range-count operations are checked against a sorted slice. After every operation the whole tree is verified for search order, the heap property, and correct sizes. Failures: 0.

Sequence Mode

Drop the keys and let the position in the in-order walk be the only order. Now splitAt(n, i) cuts by count, using the sizes, and merge needs no key comparison at all. The tree becomes an array with O(log n) operations anywhere:

func (s *Sequence) RotateLeft(k int) {
	a, b := splitAt(s.root, k)
	s.root = merge(b, a)
}

Inserting at index i, deleting the range [i, j), and rotating the array are each two or three splits and merges. The demo runs 5,000 random such operations against a Go slice and compares the full contents after every step. Failures: 0. This "implicit treap" is how text editors and some databases represent sequences that are cut and pasted often.

Other Balanced Trees

Red-black trees relax the AVL rule (the longest path may be up to twice the shortest) to make updates cheaper. They are common in language libraries, for example behind Java TreeMap and commonly behind C++ std::map. B-trees widen each node to hold many keys so that one node fills a disk page, which is why databases and file systems use them. All of them keep the same contract as the AVL tree here: an ordered set with O(log n) operations regardless of input order.

Tries: Searching by Prefix

A hash map answers "is this exact word stored?" and nothing more. To ask "which words start with car?" you would scan every key. A trie (prefix tree) stores words letter by letter: each edge is a letter, and words with a common beginning share the same path. The demo is 61_trie.go.

Six words, 20 letters, 11 nodes. The number beside a node counts the words that pass through it.

The Node

type node struct {
	next [26]*node // one slot per letter 'a'..'z'; nil means no word continues that way
	end  bool      // a stored word ends exactly here
	pass int       // how many stored words pass through (or end at) this node
}

The end flag is needed because a word can be the prefix of another: car ends in the middle of the path to card. The pass counter is an augmentation, like the size in the treap: it answers prefix counts without visiting anything below the prefix.

Insert, Contains, and Prefix Counts

func (t *Trie) Insert(w string) bool {
	if t.Contains(w) {
		return false
	}
	n := t.root
	n.pass++
	for i := 0; i < len(w); i++ {
		c := w[i] - 'a'
		if n.next[c] == nil {
			n.next[c] = &node{}
			t.nodes++
		}
		n = n.next[c]
		n.pass++
	}
	n.end = true
	t.words++
	return true
}

Every operation costs O(length of the word), not O(number of words). Contains follows the path and checks end. CountPrefix follows the path and returns pass. For the six words in the diagram, CountPrefix("car") is 3 (car, card, care) and CountPrefix("x") is 0. Note that Insert checks for a duplicate first: without that check a repeated word would inflate every counter on its path.

Autocomplete

Follow the prefix, then walk the subtree below it visiting the children in the order a to z. The words come out in alphabetical order, and the walk can stop after the first few:

func (t *Trie) Autocomplete(p string, limit int) []string {
	var out []string
	var walk func(n *node, path []byte)
	walk = func(n *node, path []byte) {
		if n == nil || len(out) >= limit {
			return
		}
		if n.end {
			out = append(out, string(path))
		}
		for c := 0; c < 26; c++ {
			walk(n.next[c], append(path, byte('a'+c)))
		}
	}
	walk(t.find(p), []byte(p))
	return out
}

The demo stores the six words of the diagram plus careful. Autocomplete("car", 10) returns [car card care careful], and with limit 2 it returns [car card]. The work depends on the length of the prefix plus the number of results returned, not on the size of the dictionary.

Delete

Walking down, decrease each pass counter. The first node whose counter reaches zero starts a chain that belonged to this word alone, so the whole chain is cut with one assignment. If the walk reaches the end with nodes still in use (other words continue below), only the end flag is cleared. Deleting car from a trie that also holds card and care removes no node at all.

Wildcards

To match a pattern such as c.r, where the dot means any letter, follow letters normally and, at a dot, try every child. The cost grows with the number of dots, not with the number of stored words.

What the Demo Measures

• Sharing. 20,000 random words over a four-letter alphabet contain 176,949 letters and use 56,440 nodes, 32% of the letters. Real dictionaries share less than that but still far more than zero.
• Oracle. 20,000 random inserts, deletes, lookups, prefix counts, autocomplete calls and wildcard searches are compared with a scan of a sorted list of words. After every operation the incremental node counter is compared to a full recount. Failures: 0.

The Memory Cost

An array of 26 pointers is 208 bytes per node on a 64-bit machine, even for a node with one child. Three common remedies: a map[byte]*node for sparse nodes, a sorted slice of children, or a compressed trie (radix tree) that merges chains of single-child nodes into one edge labelled with a string. Also, this trie accepts only lowercase a-z: a byte outside that range would index outside the array and panic. Check or normalize input first, or use a map when the alphabet is large, as with Unicode.

The Same Idea on Bits

A trie does not have to hold letters. Store the bits of a number, from the highest to the lowest, and each number is a path of length 20 (for numbers below 2²⁰). Now a question about XOR becomes a walk: to find the number that gives the largest x ^ y, go down choosing at each bit the child different from x's bit whenever it exists, because a 1 in a higher bit beats anything below it. The demo computes the largest XOR of any two numbers in an array in O(n * 20) and compares it with the O(n²) all-pairs check on 2,000 random arrays. Failures: 0.

Fenwick Trees: Prefix Sums That Change

Prefix sums (Arrays & Slices) answer a range-sum query in O(1), but one update forces an O(n) rebuild. Summing the range directly makes the update O(1) and the query O(n). A Fenwick tree, also called a binary indexed tree, makes both O(log n) using one flat array and no pointers. The demo is 62_fenwick_tree.go.

The Indexing Trick

Positions are 1-based. Slot i stores the sum of the last lowbit(i) elements ending at position i, where lowbit(i) = i & -i is the value of the lowest set bit of i. Odd positions cover one element, positions 2, 6, 10 cover two, position 4 covers four, position 8 covers eight:

A prefix query for 7 combines three slots: 2 + 14 + 9 = 25.

a       = [3 1 4 1 5 9 2 6]
tree[i] = [3 4 4 9 5 14 2 31]

Update and Prefix Query

func (f *Fenwick) Add(i, delta int) {
	for ; i < len(f.tree); i += i & -i {
		f.tree[i] += delta
	}
}

func (f *Fenwick) Prefix(i int) int {
	sum := 0
	for ; i > 0; i -= i & -i {
		sum += f.tree[i]
	}
	return sum
}

A query walks down by clearing the lowest set bit: Prefix(6) reads slot 6 (positions 5-6), then slot 4 (positions 1-4), then stops at 0. The ranges met on the way are disjoint and together cover exactly 1 to 6. An update walks up by adding the lowest set bit: changing position 4 touches slots 4 and 8, the only slots whose range contains it. Each step either clears a set bit or moves it higher, so there are at most about log₂ n steps: for n = 1,000,000 the demo finds that no query needs more than 19. A range sum is a difference of two prefixes: Range(l, r) = Prefix(r) - Prefix(l-1).

The tree can also be built from a slice in O(n): each slot pushes its finished total into the one slot that also covers it, instead of doing n separate updates.

Three More Uses

Range update, point query. Store the difference array d[i] = a[i] - a[i-1]. Adding v to every position in [l, r] changes only two differences, and the value at one position is the prefix sum of the differences:

func (f *Fenwick) RangeAdd(l, r, v int) {
	f.Add(l, v)
	if r+1 < len(f.tree) {
		f.Add(r+1, -v)
	}
}

The k-th item. If the tree stores counts (slot v holds how many times v occurs), the k-th smallest stored value is the smallest v whose prefix count reaches k. Instead of a binary search that calls Prefix each time (O(log² n)), LowerBound reads the tree directly, trying jumps of 2^k, then 2^k-1, and so on:

func (f *Fenwick) LowerBound(target int) int {
	n := len(f.tree) - 1
	pos := 0
	for step := 1 << (bits.Len(uint(n)) - 1); step > 0; step >>= 1 {
		if pos+step <= n && f.tree[pos+step] < target {
			pos += step
			target -= f.tree[pos]
		}
	}
	return pos + 1
}

This requires non-negative values, so the prefix sums never decrease.

Counting inversions. An inversion is a pair i < j with a[i] > a[j]. Replace each value by its rank so it fits the tree, then scan left to right: each element asks how many of the elements already seen are larger, which is "seen so far" minus a prefix query.

	for seen, v := range a {
		rank, _ := slices.BinarySearch(sorted, v)
		rank++ // 1-based
		count += seen - f.Prefix(rank)
		f.Add(rank, 1)
	}

The demo compares this with the O(n²) all-pairs count on 500 arrays full of duplicates (equal values are not inversions). A reversed array of 100,000 numbers has 4,999,950,000 inversions, computed with about 100,000 × 2 tree operations. Every check gives failures: 0.

Segment Trees: Any Range Operation

A Fenwick tree needs an operation that can be undone by subtraction, which suits sums but not a minimum. A segment tree works for any associative operation: sum, minimum, maximum, gcd, string concatenation, matrix product. Each node stores the answer for a range of the array and its value is op(left child, right child). The demo is 63_segment_tree.go.

A range query is answered by the few whole nodes that tile it: [1..5] = 5 + 5 + 12.

A Generic Tree

The tree needs two things from the operation: it must be associative, and it needs an identity element (0 for a sum, the largest integer for a minimum, 0 for gcd, the empty string for concatenation), which a query returns for the parts that lie outside the range.

sum := NewSeg(a, 0, func(x, y int) int { return x + y })
lo := NewSeg(a, math.MaxInt, func(x, y int) int { return min(x, y) })

An update changes one leaf and recomputes its ancestors:

func (s *Seg[T]) set(node, lo, hi, i int, v T) {
	if lo == hi {
		s.t[node] = v
		return
	}
	mid := (lo + hi) / 2
	if i <= mid {
		s.set(2*node, lo, mid, i, v)
	} else {
		s.set(2*node+1, mid+1, hi, i, v)
	}
	s.t[node] = s.op(s.t[2*node], s.t[2*node+1])
}

A query looks at each node and decides among three cases: the node is outside the query (contribute the identity), completely inside (use its stored value), or partly inside (ask both children):

func (s *Seg[T]) query(node, lo, hi, l, r int) T {
	s.visits++
	if r < lo || hi < l {
		return s.id
	}
	if l <= lo && hi <= r {
		return s.t[node]
	}
	mid := (lo + hi) / 2
	return s.op(s.query(2*node, lo, mid, l, r), s.query(2*node+1, mid+1, hi, l, r))
}

At each level at most two nodes are partly inside, so a query visits O(log n) nodes: over 20,000 random queries on 100,000 elements the demo sees at most 67 visited nodes. For a = [2 5 1 4 9 3], the sum of a[1..4] is 19 (9 nodes visited) and the minimum is 1; after setting a[2] = 10 they become 28 and 4.

The left part is always combined before the right part, so the order of the elements is preserved. That matters for a non-commutative operation: string concatenation gives "ab" and "ba" in different orders. The demo tests sum, minimum, gcd and concatenation against brute force on 300 random arrays each. Failures: 0 for all four.

Descending the Tree

Because a node stores a summary of its range, the tree can also be searched. In a maximum tree, "the first position holding a value of at least x" is one walk from the root: go left if the left child's maximum is at least x, otherwise right. That is O(log n) instead of a scan, and it is the segment-tree version of the Fenwick LowerBound.

Lazy Propagation: Range Updates

Adding a value to every element of a range by updating each leaf costs O(n). The trick is to be lazy: when a node is completely covered by the update, change its sum at once and leave a note, add[node], saying "every element below me still owes this amount". The note is delivered to the children only when a later operation has to look inside the node.

func (s *LazySum) apply(node, lo, hi, v int) {
	s.sum[node] += v * (hi - lo + 1)
	s.add[node] += v
}

func (s *LazySum) push(node, lo, hi int) {
	if s.add[node] != 0 {
		mid := (lo + hi) / 2
		s.apply(2*node, lo, mid, s.add[node])
		s.apply(2*node+1, mid+1, hi, s.add[node])
		s.add[node] = 0
	}
}

rangeAdd and query both call push before descending into a node: without it the children would answer with stale values. The demo checks range add and range sum against a plain array on 200 random arrays (failures: 0), then does something an array could not do quickly: add 3 to a million zeros, add 4 to the middle half, and ask for the total, 5,000,000 (3,000,000 plus 2,000,000), in a few tree steps.

Static Data: The Sparse Table

If the array never changes, and the operation is minimum or maximum, a sparse table answers each query with two reads. It stores, for every start position i and every power of two 2^k, the minimum of a[i .. i+2^k-1]. A query covers [l, r] with two blocks of the same power of two that may overlap:

func (s *SparseMin) Query(l, r int) int {
	k := bits.Len(uint(r-l+1)) - 1 // largest k with 2^k <= length
	return min(s.level[k][l], s.level[k][r-(1<<k)+1])
}

Overlap is harmless for minimum, maximum and gcd, because using an element twice does not change the answer. It would double-count in a sum, so sums use prefix sums or a Fenwick tree instead. The price of the speed is memory: for n = 100,000 the table stores 1,568,946 numbers, against 400,000 slots for the segment tree.

Choosing a Structure

By Situation

When Simple Is Enough

Reach for these when the simple structure is measurably too slow. A sorted slice with binary search handles a few thousand keys well, and a loop over a range is fine when queries are rare. The point of learning them is to recognize the shape of the problem: "many updates and many range questions" is a Fenwick or segment tree, and "many questions about prefixes" is a trie.

Common Pitfalls

Zero-Based Indexes in a Fenwick Tree

The Fenwick trick depends on lowbit, and the lowbit of 0 is 0. Add(0, x) never leaves position 0 and the loop runs forever. Convert positions to 1-based at the boundary of your code, once, and nowhere else.

Stale Augmented Fields

The height in the AVL tree, the size in the treap, the pass counter in the trie, and the values in a segment tree are all derived data. Every code path that changes the shape must repair them, bottom-up. When a tree gives wrong answers only after some operations, check that each function which changes a pointer also calls fix or update. The demos run a full consistency check after every operation for exactly this reason.

Forgetting to Push

In a lazy tree, reading or descending into a node without first pushing its note down uses out-of-date children. The bug appears only when a range update is followed by a query that partly overlaps it, so small tests may pass. Test with random interleaved operations.

The Wrong Identity Element

A query returns the identity for parts outside the range. Using 0 as the identity of a minimum returns 0 for every partly-outside query. The identity must satisfy op(id, x) = x: zero for sum and gcd, the largest value for min, the smallest for max, the empty string for concatenation.

Duplicates

The AVL tree and the treap here are sets: inserting an existing key changes nothing. For a multiset, store a count in each node, or make keys unique by pairing each with a serial number. In the trie, a repeated word must not increase the counters twice.

Depth of Unbalanced Trees

A plain BST fed sorted input recurses n levels deep. Go grows the stack dynamically, so it survives thousands of levels, but each level costs memory, and it is a sign that the shape needs balancing.

Practice Lab

Each exercise below breaks one detail. Predict what will fail, run the demo, and explain why that check catches it.

Run the Demos

1. In 59_avl_tree.go, delete the three lines in rebalance that rotate n.left first (the left-right case). Which row of the four-case table changes, and how many failures does the random test report?
2. In 60_treap_order_statistics.go, delete update(a) in the first branch of merge. Every result stays correct as a set of keys, so what exactly does the verification catch?
3. In 61_trie.go, delete the Contains check at the top of Insert. The small dictionary at the start still looks right. Which random check fails, and why is the failure invisible in the first example?
4. In 62_fenwick_tree.go, delete the line target -= f.tree[pos] in LowerBound. Which section fails? Then change the update position in section 2 from 1+rng.Intn(n) to rng.Intn(n) and run with timeout 5 go run 62_fenwick_tree.go. Why does the program never finish?
5. In 63_segment_tree.go, delete s.push(node, lo, hi) in rangeAdd. What does the million-element example print now, and which part of the total is lost?

Exercises

1. AVL with ranks. Add a size field to the AVL node and implement Kth and Rank. Which functions must now update it, and in what order relative to fix?
2. Sliding-window median. Use the treap to output the median of every window of k numbers in a stream. Compare with sorting each window. Values repeat in a stream, so read the Duplicates pitfall first.
3. Word search with a trie. Revisit the word-search problem from Backtracking. Build a trie of the dictionary and prune a path as soon as it is not a prefix of any word. Count the states against the version in demo 57.
4. Smaller elements to the right. For each element of an array, count how many later elements are smaller. Solve it with a Fenwick tree over ranks, scanning right to left, and check it against a double loop.
5. Range minimum with position. Change the segment tree so a query returns the index of the minimum, not only its value. What does the node type become, and what happens when two values tie?
6. Range assign. Extend LazySum with "set every element in [l, r] to v". Now a node holds two kinds of pending notes, add and assign. Which one must be cleared when the other arrives?

Continue with String Algorithms, where the tries from this lesson meet pattern matching, hashing and edit distance.