Wavelet Tree Cost

The mode in a range, and how many values below $x$ in a range, in $O(\sqrt{n})$ per query. Build is $O(n \sqrt{n})$ time and space. The array is static.

$k$-th smallest in a range, and how many values below $x$ in a range, in $O(\log \sigma)$ per query. Build is $O(n \log \sigma)$ time and space. The array is static.

Range sum, and the maximum in a range, in $O(1)$ per query. Build is $O(n \log n)$ time and space, and the array accepts point updates in $O(\log n)$.

$k$-th smallest in a range, and how many values below $x$ in a range, in $O(\log^2 n)$ per query. Build is $O(n \log n)$ time and space. The array accepts point updates.