Sum [3, 1, 4, 1, 5, 9, 2, 6] by divide and conquer: a range of one element is its own sum, anything longer splits in the middle, sums both halves recursively and adds them. Each node is a range lo-hi of indices. The tree is balanced, so its depth is about log n.
Divide and conquer range sum over 8 values.
Range 0-7 has 8 elements. Split at 3: recurse on 0-3, then on 4-7, and combine afterwards. Depth 0.
Split 0 to 7 at 3.
Range 0-3 has 4 elements. Split at 1: recurse on 0-1, then on 2-3, and combine afterwards. Depth 1.
Split 0 to 3 at 1.
Range 0-1 has 2 elements. Split at 0: recurse on 0-0, then on 1-1, and combine afterwards. Depth 2.
Split 0 to 1 at 0.
Range 0-0 holds one element, 3: nothing to split, so it is the answer.
Leaf 0.
Leaf 0 returns 3.
Range 0 to 0 returns 3.
Range 1-1 holds one element, 1: nothing to split, so it is the answer.
Leaf 1.
Leaf 1 returns 1.
Range 1 to 1 returns 1.
Combine: 0-0 gave 3 and 1-1 gave 1, so 0-1 returns 4.
Range 0 to 1 returns 4.
Range 2-3 has 2 elements. Split at 2: recurse on 2-2, then on 3-3, and combine afterwards. Depth 2.
Split 2 to 3 at 2.
Range 2-2 holds one element, 4: nothing to split, so it is the answer.
Leaf 2.
Leaf 2 returns 4.
Range 2 to 2 returns 4.
Range 3-3 holds one element, 1: nothing to split, so it is the answer.
Leaf 3.
Leaf 3 returns 1.
Range 3 to 3 returns 1.
Combine: 2-2 gave 4 and 3-3 gave 1, so 2-3 returns 5.
Range 2 to 3 returns 5.
Combine: 0-1 gave 4 and 2-3 gave 5, so 0-3 returns 9.
Range 0 to 3 returns 9.
Range 4-7 has 4 elements. Split at 5: recurse on 4-5, then on 6-7, and combine afterwards. Depth 1.
Split 4 to 7 at 5.
Range 4-5 has 2 elements. Split at 4: recurse on 4-4, then on 5-5, and combine afterwards. Depth 2.
Split 4 to 5 at 4.
Range 4-4 holds one element, 5: nothing to split, so it is the answer.
Leaf 4.
Leaf 4 returns 5.
Range 4 to 4 returns 5.
Range 5-5 holds one element, 9: nothing to split, so it is the answer.
Leaf 5.
Leaf 5 returns 9.
Range 5 to 5 returns 9.
Combine: 4-4 gave 5 and 5-5 gave 9, so 4-5 returns 14.
Range 4 to 5 returns 14.
Range 6-7 has 2 elements. Split at 6: recurse on 6-6, then on 7-7, and combine afterwards. Depth 2.
Split 6 to 7 at 6.
Range 6-6 holds one element, 2: nothing to split, so it is the answer.
Leaf 6.
Leaf 6 returns 2.
Range 6 to 6 returns 2.
Range 7-7 holds one element, 6: nothing to split, so it is the answer.
Leaf 7.
Leaf 7 returns 6.
Range 7 to 7 returns 6.
Combine: 6-6 gave 2 and 7-7 gave 6, so 6-7 returns 8.
Range 6 to 7 returns 8.
Combine: 4-5 gave 14 and 6-7 gave 8, so 4-7 returns 22.
Range 4 to 7 returns 22.
Combine: 0-3 gave 9 and 4-7 gave 22, so 0-7 returns 31.
Range 0 to 7 returns 31.
Sum 31 from 15 calls, one per node. The recurrence is T(n) = 2 T(n / 2) + O(1): each level of the tree does constant work per node and there are about 2n nodes in all, so the sum costs O(n). With O(n) combine work per level, as in merge sort, the same tree gives O(n log n).
Sum 31 after 15 calls.