Persistent Segment Tree

A persistent segment tree stores all versions—often built on compressed coordinates for k-th smallest in range.

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Merge sort tree path copying or persistent BST on values; query version t with root roots[t].

Try this in Python

from bisect import bisect_left


def kth_in_sorted_sub(arr: list[int], l: int, r: int, k: int) -> int:
    sub = sorted(arr[l : r + 1])
    return sub[k - 1]


print(kth_in_sorted_sub([3, 1, 4, 2], 0, 3, 2))

Common mistakes

• Memory blow-up if cloning whole tree.
• Wrong version index on query.

Key takeaways

• Coordinate compress values first for k-th queries.
• Pair with kth_smallest_query lesson.