38 · Segment Trees, Fenwick & String Matching
#307 Range Sum Query - Mutable
the problem
In plain words
Design a class built from an integer array that supports update(index, val) — set nums[index] = val — and sumRange(left, right) — the inclusive range sum. Calls are interleaved.
in nums = [1,3,5]; sumRange(0,2), update(1,2), sumRange(0,2)
out 9, null, 8
- 1 ≤ nums.length ≤ 3·10⁴
- -100 ≤ nums[i], val ≤ 100
- At most 3·10⁴ calls to update and sumRange
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFenwick tree (BIT)Segment tree
where this runsAdaptive arithmetic coders can keep their running symbol counts in this exact structure — the job Peter Fenwick designed it for in 1994.
Prefix sums make queries cheap but updates expensive; a plain array is the opposite. Store sums of blocks of sizes 1, 2, 4, 8… so both operations touch only O(log n) blocks.
solutions
From brute force to optimal
Update writes one cell; each query loops over the range.
- update: nums[index] = val.
- sumRange: loop left..right.
A query may scan the whole array.
The array copy.
class NumArray { private final int[] nums; public NumArray(int[] nums) { this.nums = nums.clone(); } public void update(int index, int val) { nums[index] = val; // O(1) } public int sumRange(int left, int right) { int sum = 0; for (int i = left; i <= right; i++) sum += nums[i]; // O(n) return sum; }}Split into √n chunks and keep each chunk's total.
- size = ⌈√n⌉; blocks[i / size] += nums[i].
- update: adjust one chunk total by the difference.
- query: loose values at both ends + whole chunks in the middle.
At most √n chunks plus fewer than 2√n loose values.
nums plus √n chunk totals.
class NumArray { private final int[] nums; private final int[] blocks; // blocks[b] = sum of the b-th chunk of `size` elements private final int size; public NumArray(int[] nums) { this.nums = nums.clone(); size = Math.max(1, (int) Math.ceil(Math.sqrt(nums.length))); blocks = new int[(nums.length + size - 1) / size]; for (int i = 0; i < nums.length; i++) blocks[i / size] += nums[i]; } public void update(int index, int val) { blocks[index / size] += val - nums[index]; // fix one chunk total nums[index] = val; } public int sumRange(int left, int right) { int sum = 0, i = left; while (i <= right && i % size != 0) sum += nums[i++]; // ragged start while (i + size - 1 <= right) { sum += blocks[i / size]; i += size; } // whole chunks while (i <= right) sum += nums[i++]; // ragged end return sum; }}tree[i] = sum of the lowbit(i) values ending at i. Updates climb, queries strip the lowest bit.
- Build by adding each nums[i] at position i + 1.
- update: delta = val − nums[index]; climb with i += i & -i adding delta.
- sumRange = prefix(right + 1) − prefix(left), where prefix strips bits with i -= i & -i.
Each loop changes one bit of i, so ≤ ⌊log₂ n⌋+1 iterations. Build is O(n log n) as written.
tree[n+1] plus the nums copy.
class NumArray { private final int[] nums; // current values, so "set" can become "add delta" private final int[] tree; // 1-indexed Fenwick tree (BIT) public NumArray(int[] nums) { this.nums = nums.clone(); tree = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) add(i + 1, nums[i]); } public void update(int index, int val) { int delta = val - nums[index]; nums[index] = val; add(index + 1, delta); } public int sumRange(int left, int right) { return prefix(right + 1) - prefix(left); } private void add(int i, int delta) { for (; i < tree.length; i += i & -i) // climb to the next node that covers i tree[i] += delta; } private int prefix(int i) { // sum of the first i values int sum = 0; for (; i > 0; i -= i & -i) // strip the lowest set bit sum += tree[i]; return sum; }}Dry run
A binary tree of segment sums; queries combine fully-covered nodes only.
- build: leaves copy nums, parents = left + right.
- update: walk down to the leaf, re-sum on the way back up.
- query: no overlap → 0, full overlap → node sum, partial → both children.
2n−1 nodes built once; a query visits ≤ 4 nodes per level.
A 4n int array.
class NumArray { private final int n; private final int[] tree; // tree[node] = sum of its segment; children are 2*node, 2*node+1 public NumArray(int[] nums) { n = nums.length; tree = new int[4 * Math.max(1, n)]; if (n > 0) build(nums, 1, 0, n - 1); } private void build(int[] nums, int node, int lo, int hi) { if (lo == hi) { tree[node] = nums[lo]; return; } int mid = (lo + hi) >>> 1; build(nums, 2 * node, lo, mid); build(nums, 2 * node + 1, mid + 1, hi); tree[node] = tree[2 * node] + tree[2 * node + 1]; } public void update(int index, int val) { update(1, 0, n - 1, index, val); } private void update(int node, int lo, int hi, int index, int val) { if (lo == hi) { tree[node] = val; return; } int mid = (lo + hi) >>> 1; if (index <= mid) update(2 * node, lo, mid, index, val); else update(2 * node + 1, mid + 1, hi, index, val); tree[node] = tree[2 * node] + tree[2 * node + 1]; // re-sum on the way back up } public int sumRange(int left, int right) { return query(1, 0, n - 1, left, right); } private int query(int node, int lo, int hi, int left, int right) { if (right < lo || hi < left) return 0; // no overlap if (left <= lo && hi <= right) return tree[node]; // full overlap int mid = (lo + hi) >>> 1; // partial: ask both children return query(2 * node, lo, mid, left, right) + query(2 * node + 1, mid + 1, hi, left, right); }}Segment tree dry run
in the room
How to say it in the interview
talk track
- State the trade-off table: array (O(1)/O(n)), prefix (O(n)/O(1)), and the goal O(log n)/O(log n).
- Pick Fenwick for sums and say why: smallest code. Offer the segment tree if they want min/max.
- Point out that update sets a value, so you add the difference and keep a copy of nums.
traps
- Calling add(index, val) instead of add(index, val − nums[index]).
- Using 0-based indices inside the Fenwick loops (infinite loop at 0).
what they ask next
Follow-ups
Range minimum with updates?
Segment tree with Math.min and identity Integer.MAX_VALUE. Fenwick can't, because min can't be subtracted.
2D version (LC 308)?
A 2D Fenwick tree: nested loops over rows and columns, O(log n · log m) per operation.
Can you build the Fenwick tree in O(n)?
Yes: tree[i] += nums[i−1]; then push tree[i] into its parent i + (i & −i). See RangeToolkit's Fenwick constructor.
before you submit
Edge cases to test
- One element: update it, then sumRange(0, 0)
- Updating the same index twice — the second delta must use the new value
- An update to the same value (delta 0)
- sumRange over the whole array, and over a single index
practise next
Similar problems
- #303Range Sum Query - ImmutableEasyin Hashing
- #304Range Sum Query 2D - ImmutableMediumin Hashing
- #315Count of Smaller Numbers After SelfHardin Range Queries & Strings