Prefix Sum

A complete Fenwick Tree implementation fits in fifteen lines of code, half the memory of a segment tree, and a smaller constant factor on every operation. The price of admission is that you only get prefix-style aggregates, but for the enormous class of problems that need exactly that, a **Fenwick Tree** (also called a Binary Indexed Tree, or BIT) is the right answer. This lesson covers the dynamic prefix-sum problem (static prefix sums are `O(1)` query and `O(n)` update; you want both in `O(log n)`), the `i & -i` lowbit trick that isolates the lowest set bit and implicitly defines which range each index covers, point update and prefix query in `O(log n)`, and the `prefix(R) - prefix(L-1)` identity that turns those into general range queries. You will also meet the difference-array technique that swaps the roles, supporting `O(log n)` range updates with `O(log n)` point queries. In **Arrays & Strings**, you saw how a flat array can encode rich structure when the indexing scheme is clever; the Fenwick tree pushes that idea further by letting binary representation itself carry the partition information. **Segment Tree** solved a more general version of this problem with explicit nodes; the BIT trades flexibility for simplicity and memory and wins on both metrics whenever prefix queries suffice. Next, **Sparse Table** addresses a different point in the trade space: arbitrary range minimum (and similar idempotent) queries, with `O(1)` queries when no updates are involved.

Range minimum queries on a fixed array do not need updates, so the segment tree's `O(log n)` query is leaving performance on the table. A **Sparse Table** flattens the query down to genuine `O(1)`: precompute the minimum of every power-of-2 length window, and any range `[L, R]` can be answered by combining two such windows that together cover it, exploiting the fact that `min(min(A), min(B)) = min(A union B)` when the windows overlap. This lesson covers the `O(n log n)` preprocessing that fills a 2D table indexed by `(start, log2_length)`, the `O(1)` query trick for idempotent operations such as min, max, GCD, and bitwise OR, the `log2_floor` precomputation that makes every query branch-free, and the slower `O(log n)` query needed when the operation is not idempotent (like sum). You will see why this structure is the right tool for the Range Minimum Query (RMQ) problem and an essential building block in algorithms like Lowest Common Ancestor in `O(1)` per query. In **Arrays & Strings**, a flat array stored values; here the same shape stores precomputed answers indexed by a length exponent. **Logarithms & Exponentiation** is what makes the geometry work: power-of-two windows tile the index space the way binary representations tile integers, and the `O(1)` query depends on `floor(log2(length))`. With Sparse Tables in your toolkit, the curriculum next pivots to specialized structures for strings, immutability, and bounded integer universes.

Imagine an array of a million numbers and a thousand questions of the form "what is the sum of elements between index `l` and `r`?". The naive answer loops through each query, doing roughly a billion additions in total. Prefix sums turn the same workload into a million additions plus a thousand subtractions, with answers in constant time per query. **Prefix Sum & Difference Array** covers the technique in three layers. You will build 1D prefix sums where `prefix[i] = prefix[i-1] + arr[i]` and answer any range sum in `O(1)`. You will then learn the inverse, the difference array, which turns repeated `O(n)` range updates into `O(1)` updates that you reconstruct in a single final pass. The lesson finishes with 2D prefix sums and the inclusion-exclusion trick for answering submatrix sum queries, plus quick variants like prefix XOR and prefix product. In **Arrays & Strings**, you saw why arrays support `O(1)` random access; that property is exactly what makes prefix lookup possible. **Iteration Patterns on Arrays/Strings** trained you to think in terms of single passes, and the prefix sum is the first pattern where one preprocessing pass replaces an entire family of later loops. From here you will move into **Sorting (Elementary)**, where rearranging the array unlocks an entirely different class of techniques.