Problem: You are given an array of n numbers. Answer range-sum queries and point updates in O(log n).

Input format: The first line contains n (1 ≤ n ≤ 100000). The second line contains n integers.

Output format: Print the sum of the whole array, computed through the tree.

Solution: The array is padded to a power of two and stored in a flat array of size 2·size. Leaves live in the second half; every internal node i is the sum of its children 2i and 2i+1. A range query walks the two boundaries upwards, taking whole nodes whenever a boundary falls on the odd side.

Fenwick and segment trees solve the same task. The segment tree costs twice the memory but generalises to any associative operation, not just sums.