Segment Tree

Cloning a 100k-element segment tree before every update so the previous version stays queryable costs `O(n)` time and space per update, which is unworkable. **Persistent Data Structures** achieve the same 'every past version is still queryable' guarantee in `O(log n)` extra time and space per update by sharing the unchanged subtrees between versions and only allocating new nodes along the path that actually changed. This lesson covers the path-copying technique on a persistent segment tree (each update returns a brand-new root that shares everything except a thin spine of new nodes with the previous version), the `O(log n)` point update and range query on any historical version, persistent arrays built on top of persistent segment trees, and persistent stacks and queues using the cons-list approach from functional programming. You will analyze the total space (`O(n + q log n)` for `q` updates) and apply the structure to k-th smallest in subarrays, time-travel queries, and offline-query reductions. In **Trees: Binary Tree Fundamentals**, a recursive subtree was a self-contained piece of data; structural sharing exploits exactly that property to reuse old subtrees in new versions. **Segment Tree** built the recursive aggregate-over-intervals shape that the persistent variant adapts directly, swapping in-place updates for path copying. Next, **Treap (Randomized BST)** returns to the BST family with a different twist: random priorities for expected balance and `O(log n)` split and merge primitives.

Given an array and a stream of mixed queries (`sum(L, R)`, `min(L, R)`, plus single-index updates), prefix sums answer the queries in `O(1)` but pay `O(n)` for every update, while a raw array does the opposite. Neither extreme is acceptable when both updates and queries are frequent. A **Segment Tree** balances the two: every operation runs in `O(log n)` after an `O(n)` build. This lesson covers the recursive segment-tree shape (a binary tree where each node stores the aggregate over an array interval, and children split the parent's interval in half), the `4n` flat-array layout that maps perfectly onto an iterative or recursive implementation, point update and range query in `O(log n)`, and lazy propagation, where range updates deposit a tag at the highest covering node and push it down only when a later query forces it. You will apply the structure to range sum, range minimum, and range maximum queries, and see why the same template extends to any associative aggregate. In **Arrays & Strings**, a flat array gave you `O(1)` indexed access but no aggregate support; the segment tree layers a hierarchy of precomputed aggregates on top of that array. **Trees: Binary Tree Fundamentals** is where the recursive shape and the `O(h)`-stack traversal pattern came from, and you reuse both directly here. Next, **Fenwick Tree (BIT)** solves a narrower version of the same problem (prefix-only aggregates) with simpler code and half the memory.