I think we can use "reverse-binary search" method. We using a Stack<Node> indexs to store the Nodes that at at positions 1, 2, 4, 8, 16, 32 ...., and using another stack to reversely print each region.

| 1 | 2 3 | 4 5 6 7 | 8 9 10 11 12 13 14 15 | 16 17 18 19 20 21 22 23 24 25

Thus, the time complexity is O(n), and spaces complexity is maximum at (n/2 + log(n/2)), where (n/2) is used to print the last region, and log(n/2) is used to store the indexes.

We can also using reverse binary search to print the last region if we want to save more space.