Learning Outcome
After this lesson, you should be able to split ranges into tree segments and update only affected ancestors.
Problem Statement
Design a NumArray with update(index,val) and sumRange(left,right).
| Input | Output | Why |
|---|---|---|
nums = [1,3,5], sumRange(0,2), update(1,2), sumRange(0,2) | 9, then 8 | Initial sum is 1+3+5 = 9. After changing index 1 to 2, sum is 1+2+5 = 8. |
Brute Force Approach
Compute every requested range by scanning from left to right. This costs O(n) per query.
Optimized Approach
Build a segment tree where each node stores a range sum. Point update changes one leaf and refreshes ancestors; query combines only relevant segments.
Exact Pseudocode
build(node, left, right):
if left == right:
tree[node] = nums[left]
else:
build both halves
tree[node] = sum of children
update(index, value):
walk to the leaf for index
update leaf and refresh ancestors
query(ql, qr):
return 0 for disjoint range
return node sum for fully covered range
otherwise query both halvesReference Code
class NumArray:
def __init__(self, nums):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
self._build(nums, 1, 0, self.n - 1)
def _build(self, nums, node, left, right):
if left == right:
self.tree[node] = nums[left]
return
mid = (left + right) // 2
self._build(nums, node * 2, left, mid)
self._build(nums, node * 2 + 1, mid + 1, right)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def update(self, index, val):
self._update(1, 0, self.n - 1, index, val)
def _update(self, node, left, right, index, val):
if left == right:
self.tree[node] = val
return
mid = (left + right) // 2
if index <= mid:
self._update(node * 2, left, mid, index, val)
else:
self._update(node * 2 + 1, mid + 1, right, index, val)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def sumRange(self, left, right):
return self._query(1, 0, self.n - 1, left, right)
def _query(self, node, left, right, ql, qr):
if qr < left or right < ql:
return 0
if ql <= left and right <= qr:
return self.tree[node]
mid = (left + right) // 2
return self._query(node * 2, left, mid, ql, qr) + self._query(node * 2 + 1, mid + 1, right, ql, qr)Sample Dry Run
| Step | State | Result |
|---|---|---|
| Build | root stores sum 1+3+5 | tree root = 9 |
| sumRange 0 to 2 | query fully covers root | return 9 |
| update index 1 to 2 | change leaf 3 to 2 and refresh ancestors | root becomes 8 |
| sumRange 0 to 2 | query root again | return 8 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(log n) per update or query | Each operation follows or combines a logarithmic number of tree segments. |
| Space | O(n) | The segment tree stores range sums for the array. |
Edge Cases
- A single-element range should return that element.
- Disjoint query segments should contribute 0 for sum queries.
- After update, refresh all ancestors on the path back to root.
Interview Checklist
- Define clear base cases for build, update, and query.
- Use full-cover, no-overlap, and partial-overlap cases in query.
- Allocate enough tree space, commonly 4*n.
FAQs
Why does query need three overlap cases?
It must ignore disjoint ranges, return stored sums for fully covered ranges, and split partial ranges.
Why does update refresh ancestors?
Every parent sum depends on the changed leaf, so ancestor sums must be recomputed.
What is the core pattern?
Range decomposition tree.