Allan Odgaard on finger trees: The only nodes which need updating are those on the path from the root down to the inserted node, i.e. we never update more nodes than the height of the tree which is log(n) (assuming our binary search tree is self-balancing)…