Why architecture matters here
The architecture matters because the problem it solves — keeping a running aggregate correct while the underlying data changes — is one where the obvious data structures each fail on one axis. Store the raw array and every prefix sum is a fresh loop: updates are O(1) but a query over the first million elements touches a million cells. Store a precomputed prefix-sum array and queries are a single subtraction, but a single update to element zero invalidates every prefix after it, forcing an O(n) rebuild. You cannot have both cheap updates and cheap queries with either naive layout, and in any workload that mixes reads and writes — which is nearly all of them — you pay the expensive side on every operation.
The Fenwick tree matters because it makes both operations logarithmic, which for realistic sizes is effectively free. At a billion elements, log₂(n) is about thirty, so both an update and a query touch on the order of thirty cells instead of a billion. That is not a constant-factor win; it is a change of complexity class, and it is the difference between a leaderboard that recomputes ranks in microseconds and one that stalls the request thread. The structure buys this without amortization tricks or rebalancing: every operation is worst-case O(log n), so there are no latency spikes hiding behind an average.
It also matters because it is small and simple, and those are architectural virtues, not just aesthetics. A Fenwick tree is one array of the same length as the data plus one. There are no per-node objects to allocate, no pointers to chase across the heap, no rebalancing logic to get subtly wrong. The entire implementation is two short loops. That compactness means it fits in cache, serializes trivially, and can be code-reviewed in a minute — which is exactly why it survives in production where a fancier segment tree would be overkill. When the only operations you need are point update and prefix aggregate, the Fenwick tree is the smallest thing that works, and smallest-thing-that-works is usually the right thing to ship.
Finally, the structure matters because it defines the boundary of a whole family of problems. Its power comes from the aggregate being invertible: because prefix sums subtract cleanly, a range sum is just prefix(r) - prefix(l-1). The moment you understand why that works, you also understand its limit — it does not work for max or min, because you cannot subtract a maximum out of a prefix. Knowing where the Fenwick tree applies and where you must reach for a segment tree instead is a reusable piece of judgment, and the invariant that grants its speed is the same invariant that draws that line.
The architecture: every piece explained
Top row: the data and its mirror. You have an array of counts — the mutable numbers whose prefixes you want to sum. The Fenwick tree keeps a Fenwick array of the same length (conventionally with one extra slot because it is 1-indexed), and this is the only storage the structure uses. The magic lives in what each cell means. Cell i covers a half-open range of the original array — specifically the range (i - lowbit(i), i], ending at i and stretching back a number of positions equal to the lowest set bit of i. So cell 8 (binary 1000) covers eight elements, cells 1 through 8; cell 6 (binary 110) covers two, elements 5 and 6; cell 5 (binary 101) covers just one, element 5. Each Fenwick cell stores the sum of exactly the elements in its range. The ranges nest and tile in a way dictated entirely by the binary digits of the indices.
The engine of the whole structure is lowbit(i) = i & -i, the lowest set bit of i, obtained by AND-ing i with its two's-complement negation. This single value is the length of the range cell i owns, and it is also the jump size for moving through the implicit tree. There is no separate tree data structure to store; the parent-child relationships are computed on the fly by adding or subtracting lowbit. That is why the diagram shows 'one array, no pointers' — the tree is a story the arithmetic tells about the array, not a thing that occupies memory.
Middle row: the two traversals. update(i, delta) adds delta to element i by walking upward: it updates cell i, then jumps to i += lowbit(i), updates that cell, and repeats until it walks off the end of the array. These are exactly the cells whose owned ranges include position i, so adding delta to each keeps every affected aggregate correct. prefix(i) sums the first i elements by walking downward: it reads cell i, then jumps to i -= lowbit(i), adds that cell, and repeats until i reaches zero. Because the cells it visits own disjoint ranges that tile exactly the interval [1, i], their sum is the prefix. The two loops move in opposite directions along the same bit structure, and each visits at most log n cells because each step clears or the index shrinks past a bit.
Right and bottom: composition and construction. A range(l, r) sum is not a separate mechanism — it is prefix(r) - prefix(l-1), two downward walks and a subtraction, which works only because sums are invertible. Both update and query are O(log n), about twenty steps even at a billion elements. You can build in O(n) rather than n separate updates by a linear pass that adds each cell's value into its parent cell at i + lowbit(i). And the whole thing is one array with no pointers: dense, cache-friendly, and tiny. The ops strip captures the disciplines that keep it correct: choose 0- or 1-indexing once and never mix them, guard against integer overflow in the accumulated sums, size the array at n+1 to honor the 1-indexing, and document the range-ownership invariant so the next reader is not left decoding bit tricks cold.
End-to-end flow
Trace a Fenwick tree used as a live leaderboard rank counter. Scores fall in a bounded range, and we keep a frequency array indexed by score bucket; the Fenwick tree over it lets us answer 'how many players scored at or below X' — a prefix sum — in log time, even as scores stream in.
Construction: we allocate a Fenwick array of length n+1 for n score buckets, all zeros. Rather than inserting the initial batch one point at a time (n log n), we load the raw frequencies into the array and run the O(n) build pass: for each cell i, add its value into cell i + lowbit(i) if that parent is in range. After this single linear sweep, every cell holds the sum of its owned range, and the structure is ready.
A player scores: a new result lands in bucket 5, so we call update(5, +1). The walk starts at cell 5 (binary 101, lowbit 1) and adds one. It jumps to 5 + 1 = 6 (binary 110, lowbit 2), adds one, jumps to 6 + 2 = 8 (binary 1000, lowbit 8), adds one, then jumps to 8 + 8 = 16, which is past our small example's end, so the walk stops. Three cells touched — cells 5, 6, and 8 — because those are exactly the cells whose ranges include position 5. Every prefix that should reflect the new point now does.
A rank query: we want how many players scored at or below bucket 7, i.e. prefix(7). The walk starts at cell 7 (binary 111, lowbit 1), reads it, jumps to 7 - 1 = 6 (lowbit 2), adds it, jumps to 6 - 2 = 4 (binary 100, lowbit 4), adds it, jumps to 4 - 4 = 0, and stops. Three cells — 7, 6, and 4 — whose owned ranges are {7}, {5,6}, and {1,2,3,4}, tiling [1,7] exactly and with no overlap, so their sum is precisely the count of players in buckets 1 through 7. A range query — 'players scoring between buckets 3 and 7' — is just prefix(7) - prefix(2).
What the flow shows: both the update and the query touched three cells in an eight-element example; at a million buckets each would touch about twenty. The update walked up by adding lowbit, the query walked down by subtracting it, and the cells they visited were determined entirely by the binary digits of the indices. No node was allocated, no pointer was dereferenced, and every aggregate stayed exactly consistent with the underlying frequencies. That constancy under a stream of updates — with no rebuild, no rebalancing, and no latency spike — is the whole reason the structure sits under so many running-total workloads.