Persistent Segment Tree

Path copying: each update clones only the O(log n) nodes on the root-to-leaf path (green) and shares every other subtree by pointer (blue). Old versions stay queryable forever. Second mode walks two versions to find the k-th smallest in a range.

Update: O(log n) Query: O(log n) Pick version: O(1) Mem / version: O(log n) Total: O(n + m log n)

Array:

Update — index value

K-th smallest in a[ , ] , k =

Shared (idle) node

Newly copied (this update path)

Shared with previous version

k-th descent: visited

k-th: answer leaf

log₂ n

Versions

Total nodes

Nodes copied (last upd)

Last result

Trace

Load an array to build version 0, then click + New version to watch path copying, or Find k-th to walk two versions down the value axis.

Complexity

Operation	Time	New nodes	Note
Build v0	`O(n)`	`~2n`	full tree once
Update → new version	`O(log n)`	`⌈log₂n⌉+1`	only the path is copied
Range query (any version)	`O(log n)`	`0`	same as ordinary segtree
Pick / switch version	`O(1)`	`0`	choose a root
K-th smallest in range	`O(log n)`	`0`	walk version[r] & version[l−1]
Total after m updates	—	`O(n + m log n)`	vs naive O(n·m)