LeetCode 307 ·
Medium
Range Sum Query — Mutable
Support update(index, value) and sumRange(i, j) on a mutable array.
Try it
Step through the core mechanic. The simulator below runs the segment tree shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Segment tree — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
A Fenwick (binary indexed) tree or segment tree gives O(log n) for both update and prefix-sum query. A plain prefix-sum array would make updates O(n); the tree is the point of the problem.
| Aspect | Value |
|---|---|
| Pattern | Segment tree |
| Recognise it by | Range sums with point updates — Fenwick / segment tree. |
| Time complexity | O(log n) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.