All of those operations are achievable when replacing sqrt with log by using Skip lists (https://en.wikipedia.org/wiki/Skip_list https://en.wikipedia.org/wiki/S

All of those operations are achievable when replacing sqrt with log by using Skip lists (https://en.wikipedia.org/wiki/Skip_list https://en.wikipedia.org/wiki/Skip_list), and probably with Zip trees as well (https://arxiv.org/abs/1806.06726 https://arxiv.org/abs/1806.06726). That being said, the overload of a complex data structure might multiply the running time by a factor up to ~10 (mostly because of cache misses), so simpler structures will be more performant for short inputs. There is a more general pattern in most tree data structures where you can transform the log(n) recursive operations on the tree into sqrt(n) operations on a simpler structure with 2 levels. I happen to have described the solution to a problem where you must use a sqrt-decomposition datastructure to have updates in O(1) and queries in O(sqrt(n)) because O(log(n)) everywhere is not good enough as there are a lot of updates to do (https://tryalgo.org/en/2017/09/01/path-statistics/ https://tryalgo.org/en/2017/09/01/path-statistics/).