LeetCode 307 Range Sum Query - Mutable - Solution

You build segment tree where each node stores sum of its range. Update and query in $O(\log n)$.

The core idea: tree node covers range [l, r], stores sum. Update propagates up. You query by combining relevant ranges.

Example: Array [1,3,5]. Tree: root = 9 ([0,2]), left = 4 ([0,1]), right = 5 ([2,2]). You query [0,1]: return left child = 4.

Build $O(n)$, update $O(\log n)$, query $O(\log n)$. For $n = 3 \times 10^4$, $10^4$ operations: $10^4 \times 15 \approx 1.5 \times 10^5$ operations. $O(n)$ space.