You build segment tree where each node stores sum of its range. Update and query in .
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 , update , query . For , operations: operations. space.