Fenwick Tree: Every Rank From One Array

A Fenwick tree, also called a Binary Indexed Tree, is a compact data structure for maintaining an array while answering prefix-sum queries efficiently. A useful way to understand it is through a game leaderboard.

Imagine that leaderboard positions are numbered from $1$ through $n$. At each position, an array stores a value such as the number of players at that rank, a score contribution, or another quantity that can be added together. Two operations matter:

1. Change the value at one position.
2. Ask for the total from the first position through a chosen position.

A plain scan can answer a prefix query, but it may need to inspect many positions. A traditional prefix-sum array makes queries fast, but changing one value can require many stored prefixes to be repaired. A Fenwick tree balances these two requirements. It stores carefully selected partial sums so that both a point update and a prefix query follow short paths through an array.

The central rules are:

• Every Fenwick node represents a contiguous range.
• The range length is determined by the node index's lowest set bit, called lowbit.
• A prefix query repeatedly subtracts lowbit and moves toward the beginning.
• A point update repeatedly adds lowbit and moves toward larger ranges.

The same quantity controls both directions. A query walks downward by subtracting it, while an update walks upward by adding it.

The leaderboard model​

Consider a one-dimensional array of values:

position:  1  2  3  4  5  6  7  8
value:     a  b  c  d  e  f  g  h

Write the value at position $i$ as $A[i]$. A prefix sum ending at position $r$ is

For example, a query ending at position $6$ asks for

A direct scan takes $O(r)$ time. If many queries arrive, repeatedly scanning the same prefix wastes work. A traditional prefix-sum array stores every $P(r)$, making a query $O(1)$. However, if $A[3]$ changes, every prefix beginning at position $3$ or later changes too. Repairing all of those entries can take $O(n)$ time.

The Fenwick tree stores neither every individual value in every node nor every complete prefix. Instead, it stores a collection of overlapping blocks. A prefix can be assembled from a few blocks that fit together without overlap. The binary representation of an index determines which blocks are used.

The lowbit rule​

For a positive index $i$, lowbit(i) is the value of the lowest set bit in the binary representation of $i$.

Equivalently, using bitwise operations,

This expression extracts the power of two represented by the rightmost binary $1$. Some examples are:

The important interpretation is not only the bit value. In a Fenwick tree, the node at index $i$ stores a range whose length is exactly $\operatorname{lowbit}(i)$.

Let the Fenwick array be called tree. Its fundamental invariant is

In words, the node at $i$ ends at $i$ and extends backward by its lowbit length.

For example:

• tree[1] covers position $1$ because its length is $1$.
• tree[2] covers positions $1$ through $2$ because its length is $2$.
• tree[3] covers position $3$ because its length is $1$.
• tree[4] covers positions $1$ through $4$ because its length is $4$.
• tree[6] covers positions $5$ through $6$ because its length is $2$.
• tree[8] covers positions $1$ through $8$ because its length is $8$.

For an array of length $8$, the coverage is:

The ranges overlap, and that is intentional. A prefix query does not add every overlapping range. It selects a sequence of ranges that fit together exactly.

Why the ranges end at the node index​

The right endpoint of tree[i] is always $i$. The left endpoint is

The lowbit tells us how large a power-of-two-aligned block ends at $i$. For $i=6$, the binary form is 0110, so the lowbit is $2$. The node covers two positions ending at $6$:

Therefore, tree[6] stores $A[5]+A[6]$.

For $i=12$, the binary form is 1100, and the lowbit is $4$. The node covers four positions:

So tree[12] stores the sum over positions $9$ through $12$.

This arrangement gives the implicit tree its shape. Odd indices have lowbit $1$ and store one-element blocks. Indices divisible by $2$ can store larger blocks, and powers of two store especially large prefixes. The structure is represented by an array rather than pointer-linked nodes, but the ranges still form a hierarchy of increasingly large aggregates.

Prefix queries: jumping downward by lowbit​

Suppose the request is the sum from position $1$ through position $r$. Start with index = r and answer = 0.

At every step:

1. Add tree[index] to the answer.
2. Replace index with index - lowbit(index).
3. Stop when the index becomes zero.

The index transition is

Why does this work? The current node covers the final block of the still-unprocessed prefix. Once that block is added, subtracting its length moves to the position immediately before that block.

Example: prefix through position $7$​

For $r=7$, the index sequence is

The visited nodes are $7$, $6$, and $4$. Their ranges are:

• Node $7$ covers $[7,7]$.
• Node $6$ covers $[5,6]$.
• Node $4$ covers $[1,4]$.

Together, they partition the requested prefix:

Therefore,

No position is counted twice, and no position is omitted.

The pseudocode is:

prefix_sum(index):
    answer = 0
    while index > 0:
        answer += tree[index]
        index -= lowbit(index)
    return answer

The loop does not move one position at a time. It removes one binary component at each step. That is why the number of iterations is logarithmic in the array length.

Example with numeric values​

Suppose the values are:

position:  1  2  3  4  5  6  7
value:     4  2  7  1  3  5  6

The relevant nodes for a prefix through $7$ are:

The query returns

The algorithm reaches the answer by combining stored ranges instead of scanning the seven original values.

Point updates: climbing upward by lowbit​

Now consider changing one array position. Suppose the value at position $p$ changes by an amount called $\Delta$.

If the old value is replaced by a new value, calculate

Every Fenwick node whose range contains $p$ must increase by $\Delta$. Begin at index = p. Add the change to tree[index], then move to the next larger node with

Continue while the index is within the Fenwick array.

The pseudocode is:

add(index, delta):
    while index <= n:
        tree[index] += delta
        index += lowbit(index)

This operation receives a delta, not necessarily an entirely new value. If the value at position $p$ changes from $10$ to $13$, the delta is $3$. Adding $13$ to every covering node would be incorrect because those nodes already include the old value.

Example: update position $5$​

For an array with at least $8$ positions, begin at $5$.

If $n=8$, the visited nodes are $5$, $6$, and $8$. Their ranges are:

• Node $5$ covers $[5,5]$.
• Node $6$ covers $[5,6]$.
• Node $8$ covers $[1,8]$.

Each range contains position $5$, so each stored sum receives the same delta. The next index, $16$, is outside the array and terminates the update.

Why adding lowbit finds the covering nodes​

A Fenwick node is defined by the interval ending at its own index. Starting at position $p$, the first node is the smallest stored block ending at $p$. Adding the lowbit moves to a larger block that still contains $p$.

For position $5$, the path is $5\rightarrow6\rightarrow8$. The ranges grow from a single element to two elements and then to the complete eight-element prefix. This is the Fenwick version of climbing from a local contribution to larger aggregate ranges.

The query and update paths are reverse in spirit:

• A query uses a node, then moves left by subtracting its range length.
• An update changes a position, then moves right to larger covering nodes by adding their range length.

Neither operation needs explicit pointers. The array index and bit arithmetic determine the path.

A complete small example​

Take the values:

position:  1  2  3  4  5  6  7  8
value:     2  1  4  3  6  2  5  1

The Fenwick entries are built from their defined ranges:

Now ask for the prefix through position $6$. The query path is $6\rightarrow4\rightarrow0$.

Node $6$ contributes positions $5$ and $6$, while node $4$ contributes positions $1$ through $4$:

That matches the original values:

Next, suppose position $3$ increases from $4$ to $9$. The delta is

The update path is:

Therefore, add $5$ to nodes $3$, $4$, and $8$. The affected entries become:

node 3: 4  -> 9
node 4: 10 -> 15
node 8: 24 -> 29

Nodes $3$, $4$, and $8$ all cover position $3$. Other nodes do not need modification because their ranges do not contain the changed position.

The prefix through position $6$ can now be answered with the same query path:

The original prefix was $18$, and increasing one included value by $5$ makes the new prefix $23$.

The core invariant​

The most important correctness statement is the Fenwick invariant:

Every operation should preserve this statement.

The invariant after a point update​

Suppose $A[p]$ increases by $\Delta$. A node $i$ needs to change exactly when its interval contains $p$:

For every such node, its stored range sum increases by $\Delta$. The update path visits those relevant nodes in increasing order of their coverage. Thus, after adding $\Delta$ to every visited node, the invariant remains true.

Nodes whose intervals do not contain $p$ are left untouched, as required.

The invariant during a prefix query​

At the beginning of each query iteration, the unprocessed part of the requested prefix ends at the current index. The node at that index covers the final block of that unprocessed part. Adding the node's value accounts for that block. Subtracting its lowbit moves the boundary immediately before the block.

Eventually, the index becomes zero. The visited ranges are disjoint and together cover exactly the original prefix, so their stored sums add to the requested result.

The query is correct because it partitions the prefix; it does not require every node to represent a complete prefix.

Building the Fenwick tree​

A Fenwick tree can be initialized by applying add for every array position. If there are $n$ positions, this repeated-update construction takes $O(n\log n)$ time.

The direct construction idea is:

for index from 1 through n:
    add(index, values[index])

After construction, every node must satisfy the range-sum invariant. Repeated point updates are often the easiest method to understand and trace by hand because they use the same update operation needed later.

The internal Fenwick array is normally one-based. If application data uses zero-based positions, convert an application position to an internal index before performing a query or update. The conversion must be consistent in every operation.

Range sums from two prefixes​

The basic Fenwick operation is a prefix sum, but an arbitrary contiguous range can be obtained from two prefixes. For positions $l$ through $r$,

For example, the sum over positions $3$ through $6$ is

The prefix through $2$ removes exactly the values before the requested interval. Since each prefix query takes $O(\log n)$ time, the range query also takes $O(\log n)$ time.

This formula is especially useful in the leaderboard model. A query can ask for all values through one rank, or it can ask for the total associated with a range of ranks. Both are supported by the same prefix routine.

Why one-based indexing matters​

The lowbit operation is normally applied to positive indices. Index zero is special: its lowbit is zero, so a loop that repeatedly adds or subtracts lowbit at index zero would not make progress.

For that reason, a common layout is:

application position:  0  1  2  3
Fenwick index:         1  2  3  4

The exact application-to-internal mapping can differ, but the internal Fenwick indices should normally run from $1$ through $n$. When translating an application index, apply the same convention to:

• The original value assignment.
• The point update.
• The prefix-query endpoint.
• The $l-1$ endpoint in a range query.

An off-by-one error can produce plausible results for some positions while corrupting the structure for others. Indexing is therefore part of the data structure's invariant, not merely an implementation detail.

Common mistakes​

Treating a node as a complete prefix​

tree[i] is generally not the sum from position $1$ through position $i$. It is the sum over the block ending at $i$ whose length is lowbit(i).

For example, tree[6] covers positions $5$ and $6`, not positions$1$through$6$. The complete prefix through$6$ is assembled as tree[6] + tree[4].

Walking one position at a time​

A prefix query should not decrement its index by one. The correct transition is

Likewise, an update should not increment its index by one. It must use

These jumps are what make the operations efficient and what match the stored ranges.

Adding a replacement value instead of a delta​

If a value changes from $x$ to $y$, the amount to propagate is

Propagating $y$ would double-count the old contribution already present in the affected nodes.

Forgetting the stopping condition​

A query stops when its index reaches zero. An update stops when its index exceeds $n$. These conditions are essential for termination.

Mixing zero-based and one-based positions​

If the application uses zero-based positions but the Fenwick array uses one-based indices, convert at the boundary. Do not sometimes add one and sometimes omit it. The path generated by lowbit is meaningful only for the internal index used to store the data.

Tracing the structure by hand​

When learning or debugging, write down four columns:

For a query, the next index is current minus lowbit. For an update, it is current plus lowbit. Then list the range represented by each visited node.

For a query through $7$:

query index 7: use [7,7]
query index 6: use [5,6]
query index 4: use [1,4]

For an update at $5$:

update node 5: change [5,5]
update node 6: change [5,6]
update node 8: change [1,8]

This method makes it easy to check two different properties. First, the ranges used by a query should be disjoint and should cover the requested prefix. Second, every node visited by an update should contain the changed position.

A small array of eight positions is particularly useful because the binary forms remain easy to inspect. For a larger index, the same arithmetic applies; only the number of binary digits increases.

Fenwick tree as binary decomposition​

The structure can be viewed as a binary decomposition of a prefix. The binary representation of the endpoint determines which block sizes are needed.

For example, $7$ has binary form 0111. Its query path removes the lowest set bit at each step:

The corresponding block lengths are $1$, $2$, and $4$. They add to $7$:

For endpoint $6$, the path is $6\rightarrow4\rightarrow0$. The block lengths are $2$ and $4:

This is why the selected intervals fit perfectly. The query extracts binary-sized suffix blocks from the current prefix, with the lowbit identifying the smallest block removed at each stage.

Updates use the complementary view. Starting at a position, adding lowbit moves into progressively larger ranges that include that position. Binary arithmetic identifies the next aggregate that needs the changed contribution.

This implicit binary structure explains why the data structure is called a tree even though its implementation is an array. The parent-like relationships are encoded by index transitions rather than explicit references.

Leaderboard interpretation​

Return to the leaderboard. Suppose each position represents a rank and the array contains a quantity associated with that rank. A prefix query through rank $r$ asks for the accumulated quantity from the beginning of the leaderboard through rank $r$.

If one rank's value changes, the Fenwick tree does not recalculate every prefix from that rank onward. It changes only the stored blocks that cover that rank. Later prefix queries reconstruct the correct total by combining those updated blocks.

For a query endpoint such as rank $7$, the tree might combine:

• The block for rank $7.
• The block for ranks $5$ through $6$.
• The block for ranks $1$ through $4$.

The original array remains the base sequence, while the Fenwick array provides a structured set of partial sums from which requested prefixes can be assembled. The structure is useful whenever values change at individual positions and the important aggregate is an additive prefix or interval total.

The tree does not require a pointer-linked representation. The array index and its lowbit determine a node's interval, its query predecessor, and the larger nodes affected by an update.

Complexity​

For an array of length $n$, a prefix query repeatedly removes a lowbit from its index. A point update repeatedly moves to a larger index by adding a lowbit. Both paths have logarithmic length in the standard Fenwick-tree setting.

The usual bounds are:

• Point update: $O(\log n)$.
• Prefix-sum query: $O(\log n)$.
• Range sum using two prefix sums: $O(\log n)$.
• Storage: $O(n)$.
• Repeated-update construction: $O(n\log n)$.

The important trade-off is clear. The structure uses linear storage and does not make either operation constant time, but it supports both changing one value and asking for an aggregate prefix in logarithmic time.

A compact implementation plan​

A reliable implementation can be designed in the following order.

Step 1: Choose the internal indexing convention​

Use indices from $1$ through $n$ for the Fenwick array. Decide how application positions map to those indices before writing the query and update routines.

Step 2: Implement lowbit​

The standard bitwise form is:

lowbit(index) = index & (-index)

The input should be a positive internal index during normal Fenwick traversal.

Step 3: Implement point addition​

Start at the changed position. Add the delta to the current node. Move upward by adding lowbit until the index exceeds $n$.

Step 4: Implement prefix sum​

Start at the requested endpoint. Add the current node's value. Move downward by subtracting lowbit until the index becomes zero.

Step 5: Implement range sum if needed​

Return the prefix through the right endpoint minus the prefix before the left endpoint.

Step 6: Test a tiny array by hand​

Use a short array such as eight positions. Write each node's interval, trace a query path, and trace an update path. Small binary examples expose indexing and boundary errors quickly.

Final perspective​

The Fenwick tree is compact because it stores the partial ranges needed by its two traversals. The lowbit supplies the shape:

• At node $i$, the stored interval has length $\operatorname{lowbit}(i)$.
• A prefix query consumes that interval and moves to $i-\operatorname{lowbit}(i)$.
• A point update propagates the change to larger covering nodes using $i+\operatorname{lowbit}(i)$.

The key invariant is

Once that invariant is clear, the algorithms become natural. A query partitions a prefix into disjoint stored blocks. An update changes every stored block that contains the modified position. Both operations follow binary paths of logarithmic length while using only an array.

When working with a leaderboard or any changing sequence of additive values, keep this checklist nearby:

1. Use positive, consistent internal indices.
2. Interpret each node as a lowbit-sized range ending at that node.
3. Query by subtracting lowbit.
4. Update by adding lowbit.
5. Propagate a delta for a changed value.
6. Use two prefixes to obtain an arbitrary range sum.
7. Verify the invariant on a small example before scaling up.

That combination of an explicit range invariant and implicit binary navigation is what makes the Fenwick tree an efficient tool for dynamic prefix sums.