Merge sort tree

Problems

K-Query Online¹

See also

Segment tree

External links

Lecture on Merge Sort Tree and Persistence in Data Structures By Sergey Kulik

Note that the test cases are a little bit shady, sometimes giving queries $i,j$ that don't satisfy $1\leq i\leq j\leq n$. Blue.Mary describes the correct behaviour in the comments.↩