h2. Caveats

There are more efficient solutions for the previous problems, but those are a bit more involved. The square root trick has a good balance between added complexity and algorithm speedup.

The above problems have better solutions using interval trees or some other clever tricks. The square root trick is nice, since it improves the naive solution a lot without much effort.

h2. Additional problems

# *(Level Ancestor)* You are given an tree of size $n$. $ancestor(node, levelsUp)$ finds the node’s ancestor that is $levelsUp$ steps up. For example, $ancestor(node, 1)$ returns the father and ancestor(node, 2) returns the grandfather. Implement $ancestor(node, levelsUp)$ efficiently. ($O(sqrt(n))$ per query)
# *(Range Median)* You are given an array of size $n$. Implement a data structure to perform update operations $a[i] = k$ and range median operations efficiently. The range median query, $median(l, r)$  returns the median element of the sorted subsequence $a[l..r]$. $O(log{n})$ per update and $O(sqrt(n)log(n))$ per query

h2. Try to solve Range Median and the other problems in the comments section using this trick.

h2. Try to solve Range Median and the other problems in the comments section.