p91 — Range Sum Query Mutable

Source: LeetCode 307 · Medium · Topics: Fenwick Tree (BIT), Segment Tree, Design Companies (2024–2025): Google (high), Meta (medium), Amazon (medium), Bloomberg (high) Loop position: The canonical “build a data structure” warm-up. Tests whether you’ve memorized Fenwick AND can derive segment-tree alternative on the spot.

1. Quick Context

Design a data structure supporting:

update(index, val) — set arr[index] = val.
sumRange(left, right) — return sum(arr[left..right]) inclusive.

Two solutions:

Fenwick Tree (BIT): 1-indexed array tree[] where tree[i] covers i & (-i) elements ending at i. Point update + prefix sum, both O(log n).
Iterative Segment Tree: array of size 2n. Leaves at tree[n..2n-1], internal nodes at tree[1..n-1]. Update: walk up from leaf. Query: walk up from both endpoints accumulating disjoint chunks.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/range-sum-query-mutable/

STOP. 30-min timer. Implement Fenwick from memory — no looking up i & -i.

3. Prerequisite Concepts

Two’s complement (i & -i isolates the lowest set bit).
Recursive segment tree → iterative segment tree compression.
Prefix sums as a building block.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Mutable array with O(log n) updates and O(log n) range sum.

2. Clarify: How often update vs query? If updates rare: prefix-sum + O(n) update. If queries rare: O(1) update, O(n) query. Balanced: BIT/segment tree.

3. Examples: [1,3,5], update(1, 2) → [1,2,5], sumRange(0,2)=8.

5. Brute: Store array; O(n) per query.

6. Target: O(log n) per op.

7. Pattern: BIT or segment tree.

8. Develop: see solution.py.

9. Test: all updates then all queries; interleaved; out-of-order updates.

6. Deeper Insight

6.1 Fenwick tree — the `i & -i` trick

tree[i] stores the sum of arr[i - lowbit(i) + 1 .. i] where lowbit(i) = i & -i. Update at index i propagates upward via i += lowbit(i). Prefix query at i walks down via i -= lowbit(i).

Why it works: every prefix [1..n] can be decomposed into O(log n) disjoint intervals of length lowbit. The structure is a binary-indexed forest where each node’s range is determined by its trailing zeros.

6.2 Fenwick vs segment tree

Aspect	Fenwick	Iterative Segment Tree
Code lines	~10	~20
Space	n+1	2n
Sum/prefix-sum	✅	✅
Range max/min	❌ (or hack)	✅
Range update + point query	✅ (diff trick)	✅
Range update + range query	❌ (BIT^2 hack)	✅ (lazy)

Rule: sums only → BIT. Anything else (max, min, gcd, lazy) → segment tree.

6.3 Iterative segment tree — the 2n layout

Leaves at indices [n, 2n). Internal node i has children 2i and 2i+1. Update: i = leaf; while i > 1: tree[i/2] = combine(tree[i], tree[i^1]); i /= 2. Query: walk from l += n and r += n + 1 upward, accumulating off-spine values.

6.4 Range update + point query via difference array on BIT

Store diff[i] = arr[i] - arr[i-1]. Then arr[i] = prefix_sum(diff, i). Range update [l, r] += v becomes two point updates: diff[l] += v, diff[r+1] -= v. O(log n).

6.5 Range update + range query (BIT^2)

Maintain two BITs: B1 and B2. Range update [l,r] += v: B1.update(l, v); B1.update(r+1, -v); B2.update(l, v*(l-1)); B2.update(r+1, -v*r). Range query: prefix_sum(i) = B1.prefix(i)*i - B2.prefix(i). Surprisingly clean.

6.6 Family: range query / point update DS

LC 307 Range Sum Query Mutable (this).
LC 308 Range Sum Query 2D Mutable (2D BIT or 2D segment tree).
LC 315 Count Smaller After Self (BIT over value space).
LC 327 Count of Range Sum (BIT or merge-sort).
LC 218 Skyline Problem (segment tree on heights).
LC 715 Range Module (segment tree with lazy or sorted intervals).

7. Anti-Pattern Analysis

Square root decomposition — O(√n) per op; works but signals you didn’t know BIT/segment tree.
Recompute prefix sum on update — O(n) update.
Recursive segment tree — works but verbose; iterative is the interview standard.
0-indexed BIT — possible but error-prone; use 1-indexed.
Forget that BIT stores deltas, not the array — confused initial-build code.
Build BIT in O(n log n) — possible to build in O(n) using tree[i + lowbit(i)] += tree[i].

8. Skills & Takeaways

Two implementations of the same interface.
i & -i lowbit trick.
Iterative segment tree layout.

9. When to Move On

Implement Fenwick in 10 min cold.
Implement iterative segment tree in 15 min cold.
Decide which to use based on operation type.

10. Company Context

Google: L5/L6; very common.
Meta: E5; expects BIT.
Amazon: L6.
Bloomberg: loves BIT for financial range queries.

Strong: “Fenwick (BIT) for point-update + range-sum, O(log n) each. Segment tree if I needed range max or lazy propagation. Cited BIT^2 for range-update + range-query.”

11. Interviewer’s Lens

Signal	Junior	Mid	Senior	Staff+
BIT impl	After hint	Cold	Clean + 1-indexed	+ O(n) build
Lowbit	Doesn’t know	Knows trick	Explains	+ derives from two’s complement
ST alternative	None	Mentions	Sketches	+ iterative + lazy variant
Family	None	None	LC 315	+ BIT^2 range-range

12. Level Delta

Mid (L4): BIT after a hint.
Senior (L5): Cold BIT; can sketch segment tree.
Staff (L6): + BIT^2 for range/range; + LC 308 2D.
Principal (L7+): + framing as prefix-sum query over a tree-shaped commutative monoid + recognizes BIT as a Morton-encoded prefix decomposition + can implement persistent / immutable segment tree for time-travel queries.

13. Follow-up Q&A

Q1: Range update + range query? A1: BIT^2 (two BITs) or segment tree with lazy propagation. Same O(log n).

Q2: Range max instead of sum? A2: BIT supports max in narrow case (only “max of prefix”) — segment tree is the right call.

Q3: 2D version? A3: 2D BIT — update(r,c) walks r+=lowbit(r) and c+=lowbit(c) nested. O(log² n) per op.

Q4: Online (streaming inserts at arbitrary positions)? A4: Balanced BST or order-statistic tree (skiplist, sorted-container). BIT requires fixed index space.

Q5: Persistent (query any historical version)? A5: Persistent segment tree; O(log n) per op with O(log n) extra space.

14. Solution Walkthrough

See solution.py:

NumArrayBIT — Fenwick implementation.
NumArraySegTree — iterative segment tree.
NumArrayBrute — oracle (O(n) updates/queries).

15. Beyond the Problem

Principal code review: “Range Sum Query Mutable is the smallest ‘mutable aggregate over an index space’ problem. The Staff+ insight is recognizing this as a query over a commutative monoid (here, integers under addition) on a sequential index space. Once you frame it that way, the data structure choice falls out: BIT for monoids with inverses (sum, XOR), segment tree for monoids without inverses (max, min, gcd, set union). The lesson scales: when you face any ‘mutable array with aggregate queries’ problem — financial OHLC bars, real-time analytics, ad-auction histograms, time-series DB — the answer is a segment tree or BIT, and the only question is whether your aggregation has an inverse. Real systems: ClickHouse / DuckDB use column-oriented segment trees for analytical queries; Redis ZADD uses a skiplist (similar O(log n) tradeoff); ad-tech systems use 2D BITs for geographic + temporal aggregations. Knowing this pattern lets you design these systems from scratch.”

LeetCode Interview — Extreme Coding