Hints — p91 Range Sum Query Mutable

1. O(n) per query is too slow for many queries; O(n) per update is too slow if frequent. Need O(log n) for both.

2. Fenwick Tree (BIT): 1-indexed array where tree[i] stores the sum of a range ending at i of length lowbit(i) = i & -i. Update propagates i += lowbit(i); prefix sum walks i -= lowbit(i).

3. Iterative Segment Tree: 2n-node array. Leaves at [n, 2n). Internal node i aggregates tree[2i] and tree[2i+1]. Range query: walk both endpoints upward, accumulate off-spine nodes.

4. Range sum [l, r] via BIT = prefix(r+1) - prefix(l) using 1-indexed inclusive prefix.

5. Choice: BIT for sum/XOR (has inverse); segment tree for max/min/gcd (no inverse) or for lazy propagation (range updates).

If stuck: see solution.py.