Loading…

mediumTreesSometimes asked

Fenwick Tree (Binary Indexed Tree)

Q: How do you solve Fenwick Tree (Binary Indexed Tree) using the Baseline — Prefix-Sum Array (Rebuild on Update) approach?

When to use it: State this first: it is the obvious structure and it exposes exactly which operation hurts, motivating the BIT. The first idea for prefix sums is a precomputed prefix array. **Queries are instant.** With `prefix[i]` stored, `prefix(i)` is one array read — O(1). For a static array this is unbeatable. **Updates are the problem.** Changing `a[i]` by `delta` changes every prefix from `i` onward: `prefix[i], prefix[i+1], …, prefix[n]` all increase by `delta`. Repairing them is an O(n) sweep. **Why this fails the problem.** The operations are interleaved and there are up to 10⁵ updates. Each O(n) repair gives up to 10¹⁰ total work. The plain (non-prefix) array flips the costs — O(1) update, O(n) query — but is equally bad when queries are frequent. **What the Fenwick tree fixes.** We want *both* sub-linear. The BIT stores partial sums over power-of-two-sized blocks so that an update touches only the O(log n) blocks containing index i, and a query reads only the O(log n) blocks that tile `[1, i]`. Time complexity: O(1) query, O(n) update. Space complexity: O(n).

Trees & BST · 27 of 41 · 11 min

Maintain a Fenwick tree (Binary Indexed Tree) over an array a[1..n] supporting:

1
**update(i, delta)** — add delta to a[i].
2
**prefix(i)** — return a[1] + a[2] + … + a[i].
3
**rangeSum(l, r)** — return a[l] + … + a[r], computed as prefix(r) − prefix(l − 1).

Each of the first two operations must run in **O(log n)**. Explain the lowbit = i & -i trick that makes this work.

In plain English

We want prefix sums that survive point updates without an O(n) rebuild. A Fenwick tree assigns to each index i responsibility for a contiguous block of `i & -i` elements ending at i. Because every prefix `[1, i]` decomposes into exactly the blocks indicated by the set bits of i, a prefix query reads O(log n) cells, and a point update touches the O(log n) blocks that contain that index.

Examples

Example 1

Input: a = [_,1,3,5,7,9,11] (1-based); prefix(3)
Output: 9
Note: a[1] + a[2] + a[3] = 1 + 3 + 5 = 9.

Example 2

Input: update(2, +7) then prefix(3)
Output: 16
Note: a[2] becomes 10, so 1 + 10 + 5 = 16.

Example 3

Input: rangeSum(2, 4)
Output: 15
Note: prefix(4) − prefix(1) = 16 − 1 = 15 on the original array (3 + 5 + 7).

Constraints

1 ≤ n ≤ 10⁵ (or larger; the structure scales to ~10⁶ comfortably)
Indices are 1-based: valid i is in [1, n]
Up to 10⁵ interleaved update and query calls
Sums fit in 64-bit (use long in Java)

Clarifying questions4First question: Is the array indexed from 0 or 1?Explore questions

Q1.Is the array indexed from 0 or 1?
1-based for the Fenwick tree itself. Index 0 has lowbit 0, which makes the update loop never advance — so I shift external 0-based indices by +1.
Q2.Are updates 'add delta' or 'set value'?
The primitive is 'add delta'. To set a[i] = v, compute delta = v − current(i) and add that. Storing absolute values directly would corrupt the partial sums.
Q3.Do we need range min/max too?
No — Fenwick excels at invertible aggregates like sum and xor. For range min/max use a segment tree, since prefix subtraction does not recover a min.
Q4.How large can n get?
The loops are O(log n) and the array is size n+1, so n up to ~10⁶ is comfortable. No recursion, so no stack-depth concern.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A Fenwick tree (Binary Indexed Tree) answers prefix-sum queries and point updates in O(log n) each, using a single array and one bit trick. Each index i is responsible for a block of `lowbit(i) = i & -i` elements ending at i. To query prefix(i), jump i down by removing its lowest set bit each step; to update index i, jump up by adding its lowest set bit. It is shorter than a segment tree for the point-update + prefix-sum case. Use 1-based indexing.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand the lowbit decomposition — that index i covers the block of size i & -i ending at i — and can explain why update and query walk in opposite directions, all on 1-based indices.

Where candidates slip

Using 0-based indexing so lowbit(0) = 0 spins forever, or moving in the wrong direction (descending on update), or storing absolute values instead of deltas.

How to stand out

Derive the structure from the binary representation: prefix(i) splits into O(log n) blocks, one per set bit of i. Mention that two Fenwick trees give range-update + range-query, and that it is the standard tool for counting inversions.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Prefix-Sum Array (Rebuild on Update)	`O(1) query, O(n) update`	`O(n)`	State this first: it is the obvious structure and it exposes exactly which operation hurts, motivating the BIT.	Read
2	Fenwick Tree — lowbit Jumps (Optimal)Optimal	`O(n) build, O(log n) update, O(log n) query`	`O(n)`	The answer they want for point update + prefix sum. 'Each index owns a block of i & -i elements; update climbs, query descends.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Which block each index owns (lowbit)

How to read it:Index i covers the i & -i elements ending at i. prefix(7) reads bit[7] + bit[6] + bit[4]: blocks of size 1, 2, 4.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Prefix-Sum Array (Rebuild on Update)

TimeO(1) query, O(n) updateSpaceO(n)

State this first: it is the obvious structure and it exposes exactly which operation hurts, motivating the BIT.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Precompute prefix[i] = a[1] + … + a[i]. Then prefix(i) is a single array read — O(1).

2Hint 2Explore hint

But update(i, delta) changes a[i], which shifts prefix[i], prefix[i+1], …, prefix[n] — every later prefix. That is O(n) per update.

3Hint 3Explore hint

Symmetrically, storing the raw array makes updates O(1) but queries O(n). Neither is good when both operations are frequent.

A · Core idea

The first idea for prefix sums is a precomputed prefix array.

Queries are instant. With prefix[i] stored, prefix(i) is one array read — O(1). For a static array this is unbeatable.

Updates are the problem. Changing a[i] by delta changes every prefix from i onward: prefix[i], prefix[i+1], …, prefix[n] all increase by delta. Repairing them is an O(n) sweep.

Why this fails the problem. The operations are interleaved and there are up to 10⁵ updates. Each O(n) repair gives up to 10¹⁰ total work. The plain (non-prefix) array flips the costs — O(1) update, O(n) query — but is equally bad when queries are frequent.

What the Fenwick tree fixes. We want both sub-linear. The BIT stores partial sums over power-of-two-sized blocks so that an update touches only the O(log n) blocks containing index i, and a query reads only the O(log n) blocks that tile [1, i].

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [_,1,3,5,7] (1-based); prefix array, then update(2,+7)

build prefix

prefix = [_,1,4,9,16]

Stateready

Final resultquery O(1), update O(n)

C · Code with teaching comments

Reference implementation previewclass PrefixArray { private final long[] prefix; private final int n; PrefixArray(int[] a) { // a is 1-based: a[0] unusedExplore the full code

solution.javaJava

Baseline — Prefix-Sum Array (Rebuild on Update) — reference

3 teaching notes

1
class PrefixArray {
2
    private final long[] prefix;
3
    private final int n;
4
 
5
    PrefixArray(int[] a) {         // a is 1-based: a[0] unused
6
        n = a.length - 1;
7
        prefix = new long[n + 1];
8
        for (int i = 1; i <= n; i++) {
9
            // Standard prefix build — O(n) once.
10
            prefix[i] = prefix[i - 1] + a[i];
11
        }
12
    }
13
 
14
    long prefix(int i) {            // O(1)
15
        // Query is a single read — the fast side.
16
        return prefix[i];
17
    }
18
 
19
    void update(int i, int delta) { // O(n): fix every later prefix
20
        // Every prefix from i to n must change — the O(n) that the BIT removes.
21
        for (int j = i; j <= n; j++) {
22
            prefix[j] += delta;
23
        }
24
    }
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(1) query, O(n) update timeO(n) spaceOpen the invariant and proofExplore the proof

The prefix-sum array and the raw array are the two extremes: O(1)/O(n) and O(n)/O(1). The Fenwick tree pays a logarithm on both sides by chopping the prefix into blocks whose sizes are powers of two — exactly the set bits of the index.

ComplexityO(1) query, O(n) update time, O(n) space — A prefix-sum array answers queries by one read (O(1)) but any single update invalidates all suffix prefixes, costing O(n) to repair. With q updates that is O(q·n).

E · Edge cases and pitfalls3Thinking O(1) queries make this good enough — updates are O(n) and dominate.Explore edge cases

Pitfalls

Thinking O(1) queries make this good enough — updates are O(n) and dominate.
Mixing 0-based and 1-based indexing between the array and prefixes.
Forgetting that 'set value' differs from 'add delta' when repairing prefixes.

03.2

Approach 2 of 2 · Optimal

Fenwick Tree — lowbit Jumps (Optimal)

TimeO(n) build, O(log n) update, O(log n) querySpaceO(n)

The answer they want for point update + prefix sum. 'Each index owns a block of i & -i elements; update climbs, query descends.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Give index i responsibility for the block of elements ending at i with length lowbit(i) = i & -i (the value of its lowest set bit).

2Hint 2Explore hint

To query prefix(i), repeatedly add bit[i] and strip the lowest set bit: i -= i & -i, until i hits 0. The blocks visited tile [1, i] exactly.

3Hint 3Explore hint

To update index i, repeatedly add delta to bit[i] and add the lowest set bit: i += i & -i, until i exceeds n. Those are the blocks that contain i.

A · Core idea

A Fenwick tree (Binary Indexed Tree) is an array bit[1..n] where each index secretly owns a block of consecutive elements, and the block boundaries come straight from binary representation.

The lowbit idea. Define lowbit(i) = i & -i. In two's complement, -i flips all bits of i and adds 1, so i & -i isolates the lowest set bit of i. For example lowbit(6) = lowbit(110₂) = 010₂ = 2. We declare that bit[i] stores the sum of the block a[i − lowbit(i) + 1 .. i] — a run of lowbit(i) elements ending at i. So bit[4] (lowbit 4) covers [1,4], bit[6] (lowbit 2) covers [5,6], bit[7] (lowbit 1) covers [7,7].

Why a prefix query is O(log n). To get prefix(i) = a[1..i], start at i and add bit[i] (the block ending at i), then jump to i − lowbit(i) — the index just before that block — and repeat. Each jump removes the lowest set bit, so the number of jumps equals the number of set bits in i, at most log₂ n. The blocks visited are disjoint and tile [1, i] perfectly. For i = 7 = 111₂ we read bit[7] (size 1), bit[6] (size 2), bit[4] (size 4) — three reads for a 7-element prefix.

Why a point update is O(log n). Adding delta to a[i] must update every block that contains i. Those are found by repeatedly adding the lowest set bit: i, i + lowbit(i), …. Each step moves to the next-larger block that swallows the current one, and again there are at most log₂ n such blocks before exceeding n. Update climbs; query descends — opposite directions over the same lowbit step.

Why 1-based indexing is mandatory. lowbit(0) = 0, so an update starting at index 0 would do i += 0 forever. Anchoring the tree at index 1 (and shifting any external 0-based index by +1) avoids the infinite loop and makes the block math clean.

Range sums by subtraction. Because sum is invertible, rangeSum(l, r) = prefix(r) − prefix(l − 1). This is exactly why Fenwick trees are restricted to invertible aggregates: you cannot recover a range minimum by subtracting two prefix minima.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 7, all zero; update(3,+5); then prefix(7)

Array state

i=3

bit[3] += 5; next 3 + 1 = 4

[0]

[1]

[2]

i ↓

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final resultprefix(7) = 5

C · Code with teaching comments

solution.javaJava

Fenwick Tree — lowbit Jumps (Optimal) — optimal

5 teaching notes

1
class FenwickTree {
2
    private final long[] bit;
3
    private final int n;
4
 
5
    FenwickTree(int n) {
6
        this.n = n;
7
        // Size n+1 so valid indices are 1..n; index 0 is never visited (lowbit 0
8
        // loops).
9
        this.bit = new long[n + 1];   // 1-based; index 0 unused
10
    }
11
 
12
    // Build in O(n) from a 1-based array a[1..n].
13
    FenwickTree(int[] a) {
14
        this(a.length - 1);
15
        for (int i = 1; i <= n; i++) {
16
            bit[i] += a[i];
17
            // O(n) build: each block forwards its sum to the next block that contains
18
            // it.
19
            int parent = i + (i & -i);
20
            if (parent <= n) {
21
                bit[parent] += bit[i];
22
            }
23
        }
24
    }
25
 
26
    void update(int i, long delta) {   // climb: add lowbit
27
        // Update climbs by adding the lowest set bit — the O(log n) blocks containing
28
        // i.
29
        for (; i <= n; i += i & -i) {
30
            bit[i] += delta;
31
        }
32
    }
33
 
34
    long prefix(int i) {               // descend: strip lowbit
35
        long sum = 0;
36
        // Query descends by stripping the lowest set bit — the O(log n) blocks tiling
37
        // [1, i].
38
        for (; i > 0; i -= i & -i) {
39
            sum += bit[i];
40
        }
41
        return sum;
42
    }
43
 
44
    long rangeSum(int l, int r) {
45
        // Range sum via subtraction — valid only because sum is invertible.
46
        return prefix(r) - prefix(l - 1);
47
    }
48
 
49
    public static void main(String[] args) {
50
        // a[1..6] = 1,3,5,7,9,11
51
        FenwickTree ft = new FenwickTree(new int[]{0, 1, 3, 5, 7, 9, 11});
52
        System.out.println(ft.prefix(3));    // 9
53
        ft.update(2, 7);                     // a[2] -> 10
54
        System.out.println(ft.prefix(3));    // 16
55
        System.out.println(ft.rangeSum(2, 4)); // 10+5+7 = 22
56
    }
57
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.57 lines

D · Why it works and complexityO(n) build, O(log n) update, O(log n) query timeO(n) spaceOpen the invariant and proofExplore the proof

The whole structure is binary arithmetic in disguise: the set bits of an index tell you both how to split a prefix into blocks (query, descending) and which blocks own an element (update, ascending). That single i & -i operation replaces all the explicit child/parent pointers a segment tree needs — which is why the code is so short and the constant factor so small.

ComplexityO(n) build, O(log n) update, O(log n) query time, O(n) space — Stripping or adding the lowest set bit changes the number of set bits / magnitude so that at most O(log n) iterations occur (one per bit position). Each iteration is O(1). Build can be done in O(n) by propagating each value to its parent, or O(n log n) by n updates.

E · Edge cases and pitfalls7update at index 0 — Bug trap: lowbit(0) = 0 means i never advances → infinite loop. Always keep the tree 1-based.Explore edge cases

Edge cases handled

update at index 0Bug trap: lowbit(0) = 0 means i never advances → infinite loop. Always keep the tree 1-based.
prefix(0)Loop condition i > 0 is immediately false → returns 0, the correct empty-prefix sum.
rangeSum(1, n)prefix(n) − prefix(0) = whole-array sum; prefix(0) safely returns 0.

Pitfalls

0-based indexing — lowbit(0) = 0 causes the update loop to never terminate.
Swapping the directions — climbing on query or descending on update gives wrong sums.
Storing absolute values in update instead of deltas — compute delta = new − old to set a value.
Using int for sums in Java when totals exceed 2³¹ — use long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass FenwickTree { private final long[] bit; private final int n; FenwickTree(int n) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

class FenwickTree {
    private final long[] bit;
    private final int n;

FenwickTree(int n) {
        this.n = n;
        this.bit = new long[n + 1];   // 1-based; index 0 unused
    }

// Build in O(n) from a 1-based array a[1..n].
    FenwickTree(int[] a) {
        this(a.length - 1);
        for (int i = 1; i <= n; i++) {
            bit[i] += a[i];
            int parent = i + (i & -i);
            if (parent <= n) {
                bit[parent] += bit[i];
            }
        }
    }

void update(int i, long delta) {   // climb: add lowbit
        for (; i <= n; i += i & -i) {
            bit[i] += delta;
        }
    }

long prefix(int i) {               // descend: strip lowbit
        long sum = 0;
        for (; i > 0; i -= i & -i) {
            sum += bit[i];
        }
        return sum;
    }

long rangeSum(int l, int r) {
        return prefix(r) - prefix(l - 1);
    }

public static void main(String[] args) {
        // a[1..6] = 1,3,5,7,9,11
        FenwickTree ft = new FenwickTree(new int[]{0, 1, 3, 5, 7, 9, 11});
        System.out.println(ft.prefix(3));    // 9
        ft.update(2, 7);                     // a[2] -> 10
        System.out.println(ft.prefix(3));    // 16
        System.out.println(ft.rangeSum(2, 4)); // 10+5+7 = 22
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Zero-based indexing infinite loop

lowbit(0) = 0 & -0 = 0, so 'i += i & -i' leaves i at 0 forever. The Fenwick tree must be 1-based; shift any external 0-based index by +1 before calling.

Explore the code comparison

Don't write this

def update(self, i, delta):   # i passed as 0-based
    while i < self.n:
        self.bit[i] += delta
        i += i & -i           # i stays 0 forever when i == 0

Write this instead

def update(self, i, delta):   # i is 1-based
    while i <= self.n:
        self.bit[i] += delta
        i += i & -i

Wrong jump direction

Update touches the blocks that contain i (climb by adding lowbit); query reads the blocks that tile [1, i] (descend by stripping lowbit). Swapping them reads the wrong cells and returns garbage.

Explore the code comparison

Don't write this

long prefix(int i) {
    long s = 0;
    for (; i <= n; i += i & -i) s += bit[i];  // wrong: climbing on a query
    return s;
}

Write this instead

long prefix(int i) {
    long s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];   // descend on a query
    return s;
}

Absolute value instead of delta

update adds delta into every covering block. Passing the new absolute value double-counts the old contribution. To set a[i] = v, add v − current(i).

Explore the code comparison

Don't write this

def set_value(self, i, v):
    self.update(i, v)            # adds v on top of the old value

Write this instead

def set_value(self, i, v):
    current = self.range_sum(i, i)
    self.update(i, v - current)  # add only the difference

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Implicit tree over an array via the lowest-set-bit (i & -i) jump

Code pattern to memorize

update(i, delta):           # i is 1-based
    while i <= n: bit[i] += delta; i += i & -i
prefix(i):                  # sum of a[1..i]
    s = 0
    while i > 0: s += bit[i]; i -= i & -i
    return s

Rules to remember

1Use 1-based indexing — index 0 has lowbit(0) = 0, which would loop forever.
2lowbit(i) = i & -i isolates the lowest set bit; that value is the size of the block node i covers.
3update climbs by i += i & -i (toward n); query descends by i -= i & -i (toward 0). Opposite directions.
4A range sum [l, r] is prefix(r) − prefix(l − 1) — two prefix queries.
5Store deltas in update: bit[i] += delta, not = val. To set a value, first compute the difference from the current value.

Use this pattern when

Point updates plus prefix-sum (or range-sum) queries, interleaved
Counting inversions, or 'how many seen so far are ≤ x' while streaming
Coordinate-compressed frequency counts with running totals
When you want segment-tree power for sums but with shorter, cache-friendly code

Choose another pattern when

Need range min/max, not sum → Fenwick does not support arbitrary range min cleanly; use a segment tree
Need range updates + range queries → a lazy segment tree is the cleaner fit (or a two-BIT trick)
Array is static → a prefix-sum array gives O(1) queries with no structure
Non-invertible aggregate (e.g. max with deletions) → prefix subtraction breaks down

Interview takeaway

The Fenwick tree is the minimalist's segment tree for sums: one array, two five-line loops, and the `i & -i` trick that lets each index own a power-of-two-sized block. It trades the segment tree's generality for half the code and a smaller constant factor.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFenwick tree / Binary Indexed Tree: an implicit tree over an array where index i owns a block of i & -i elements. Update climbs by adding the lowest set bit, prefix query descends by stripping it — both O(log n). The minimalist tool for point update + prefix/range sum on invertible aggregates (sum, xor).

Practice queueDirect variations and pattern siblings

Direct follow-ups

Range Sum Query - Mutable
Coming soon
The canonical point-update + range-sum problem — a Fenwick tree is the shortest solution.
Count of Smaller Numbers After Self
Coming soon
Coordinate-compress, then a BIT over value-frequencies counts how many smaller values appeared.
Range Update + Range Query (two BITs)
Coming soon
Maintain two Fenwick trees to support adding to a range and querying a range sum, both O(log n).
Segment Tree for Range Sum
The more general structure — use it when you need range min/max or lazy range updates.

Same pattern

←

Euler Tour of a Tree (Subtree Flattening)

Continue · Next problem

Heavy-Light Decomposition (Path Queries)

mediumTreesSometimes asked

Fenwick Tree (Binary Indexed Tree)

Trees & BST · 27 of 41 · 11 min

Maintain a Fenwick tree (Binary Indexed Tree) over an array a[1..n] supporting:

1
**update(i, delta)** — add delta to a[i].
2
**prefix(i)** — return a[1] + a[2] + … + a[i].
3
**rangeSum(l, r)** — return a[l] + … + a[r], computed as prefix(r) − prefix(l − 1).

Each of the first two operations must run in **O(log n)**. Explain the lowbit = i & -i trick that makes this work.

In plain English

Examples

Example 1

Input: a = [_,1,3,5,7,9,11] (1-based); prefix(3)
Output: 9
Note: a[1] + a[2] + a[3] = 1 + 3 + 5 = 9.

Example 2

Input: update(2, +7) then prefix(3)
Output: 16
Note: a[2] becomes 10, so 1 + 10 + 5 = 16.

Example 3

Input: rangeSum(2, 4)
Output: 15
Note: prefix(4) − prefix(1) = 16 − 1 = 15 on the original array (3 + 5 + 7).

Constraints

1 ≤ n ≤ 10⁵ (or larger; the structure scales to ~10⁶ comfortably)
Indices are 1-based: valid i is in [1, n]
Up to 10⁵ interleaved update and query calls
Sums fit in 64-bit (use long in Java)

Clarifying questions4First question: Is the array indexed from 0 or 1?Explore questions

Q1.Is the array indexed from 0 or 1?
1-based for the Fenwick tree itself. Index 0 has lowbit 0, which makes the update loop never advance — so I shift external 0-based indices by +1.
Q2.Are updates 'add delta' or 'set value'?
The primitive is 'add delta'. To set a[i] = v, compute delta = v − current(i) and add that. Storing absolute values directly would corrupt the partial sums.
Q3.Do we need range min/max too?
No — Fenwick excels at invertible aggregates like sum and xor. For range min/max use a segment tree, since prefix subtraction does not recover a min.
Q4.How large can n get?
The loops are O(log n) and the array is size n+1, so n up to ~10⁶ is comfortable. No recursion, so no stack-depth concern.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Using 0-based indexing so lowbit(0) = 0 spins forever, or moving in the wrong direction (descending on update), or storing absolute values instead of deltas.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Prefix-Sum Array (Rebuild on Update)	`O(1) query, O(n) update`	`O(n)`	State this first: it is the obvious structure and it exposes exactly which operation hurts, motivating the BIT.	Read
2	Fenwick Tree — lowbit Jumps (Optimal)Optimal	`O(n) build, O(log n) update, O(log n) query`	`O(n)`	The answer they want for point update + prefix sum. 'Each index owns a block of i & -i elements; update climbs, query descends.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Which block each index owns (lowbit)

How to read it:Index i covers the i & -i elements ending at i. prefix(7) reads bit[7] + bit[6] + bit[4]: blocks of size 1, 2, 4.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Prefix-Sum Array (Rebuild on Update)

TimeO(1) query, O(n) updateSpaceO(n)

State this first: it is the obvious structure and it exposes exactly which operation hurts, motivating the BIT.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Precompute prefix[i] = a[1] + … + a[i]. Then prefix(i) is a single array read — O(1).

2Hint 2Explore hint

But update(i, delta) changes a[i], which shifts prefix[i], prefix[i+1], …, prefix[n] — every later prefix. That is O(n) per update.

3Hint 3Explore hint

Symmetrically, storing the raw array makes updates O(1) but queries O(n). Neither is good when both operations are frequent.

A · Core idea

The first idea for prefix sums is a precomputed prefix array.

Queries are instant. With prefix[i] stored, prefix(i) is one array read — O(1). For a static array this is unbeatable.

Updates are the problem. Changing a[i] by delta changes every prefix from i onward: prefix[i], prefix[i+1], …, prefix[n] all increase by delta. Repairing them is an O(n) sweep.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [_,1,3,5,7] (1-based); prefix array, then update(2,+7)

build prefix

prefix = [_,1,4,9,16]

Stateready

Final resultquery O(1), update O(n)

C · Code with teaching comments

Reference implementation previewclass PrefixArray { private final long[] prefix; private final int n; PrefixArray(int[] a) { // a is 1-based: a[0] unusedExplore the full code

solution.javaJava

Baseline — Prefix-Sum Array (Rebuild on Update) — reference

3 teaching notes

1
class PrefixArray {
2
    private final long[] prefix;
3
    private final int n;
4
 
5
    PrefixArray(int[] a) {         // a is 1-based: a[0] unused
6
        n = a.length - 1;
7
        prefix = new long[n + 1];
8
        for (int i = 1; i <= n; i++) {
9
            // Standard prefix build — O(n) once.
10
            prefix[i] = prefix[i - 1] + a[i];
11
        }
12
    }
13
 
14
    long prefix(int i) {            // O(1)
15
        // Query is a single read — the fast side.
16
        return prefix[i];
17
    }
18
 
19
    void update(int i, int delta) { // O(n): fix every later prefix
20
        // Every prefix from i to n must change — the O(n) that the BIT removes.
21
        for (int j = i; j <= n; j++) {
22
            prefix[j] += delta;
23
        }
24
    }
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(1) query, O(n) update timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Thinking O(1) queries make this good enough — updates are O(n) and dominate.Explore edge cases

Pitfalls

Thinking O(1) queries make this good enough — updates are O(n) and dominate.
Mixing 0-based and 1-based indexing between the array and prefixes.
Forgetting that 'set value' differs from 'add delta' when repairing prefixes.

03.2

Approach 2 of 2 · Optimal

Fenwick Tree — lowbit Jumps (Optimal)

TimeO(n) build, O(log n) update, O(log n) querySpaceO(n)

The answer they want for point update + prefix sum. 'Each index owns a block of i & -i elements; update climbs, query descends.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Give index i responsibility for the block of elements ending at i with length lowbit(i) = i & -i (the value of its lowest set bit).

2Hint 2Explore hint

To query prefix(i), repeatedly add bit[i] and strip the lowest set bit: i -= i & -i, until i hits 0. The blocks visited tile [1, i] exactly.

3Hint 3Explore hint

To update index i, repeatedly add delta to bit[i] and add the lowest set bit: i += i & -i, until i exceeds n. Those are the blocks that contain i.

A · Core idea

A Fenwick tree (Binary Indexed Tree) is an array bit[1..n] where each index secretly owns a block of consecutive elements, and the block boundaries come straight from binary representation.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 7, all zero; update(3,+5); then prefix(7)

Array state

i=3

bit[3] += 5; next 3 + 1 = 4

[0]

[1]

[2]

i ↓

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final resultprefix(7) = 5

C · Code with teaching comments

solution.javaJava

Fenwick Tree — lowbit Jumps (Optimal) — optimal

5 teaching notes

1
class FenwickTree {
2
    private final long[] bit;
3
    private final int n;
4
 
5
    FenwickTree(int n) {
6
        this.n = n;
7
        // Size n+1 so valid indices are 1..n; index 0 is never visited (lowbit 0
8
        // loops).
9
        this.bit = new long[n + 1];   // 1-based; index 0 unused
10
    }
11
 
12
    // Build in O(n) from a 1-based array a[1..n].
13
    FenwickTree(int[] a) {
14
        this(a.length - 1);
15
        for (int i = 1; i <= n; i++) {
16
            bit[i] += a[i];
17
            // O(n) build: each block forwards its sum to the next block that contains
18
            // it.
19
            int parent = i + (i & -i);
20
            if (parent <= n) {
21
                bit[parent] += bit[i];
22
            }
23
        }
24
    }
25
 
26
    void update(int i, long delta) {   // climb: add lowbit
27
        // Update climbs by adding the lowest set bit — the O(log n) blocks containing
28
        // i.
29
        for (; i <= n; i += i & -i) {
30
            bit[i] += delta;
31
        }
32
    }
33
 
34
    long prefix(int i) {               // descend: strip lowbit
35
        long sum = 0;
36
        // Query descends by stripping the lowest set bit — the O(log n) blocks tiling
37
        // [1, i].
38
        for (; i > 0; i -= i & -i) {
39
            sum += bit[i];
40
        }
41
        return sum;
42
    }
43
 
44
    long rangeSum(int l, int r) {
45
        // Range sum via subtraction — valid only because sum is invertible.
46
        return prefix(r) - prefix(l - 1);
47
    }
48
 
49
    public static void main(String[] args) {
50
        // a[1..6] = 1,3,5,7,9,11
51
        FenwickTree ft = new FenwickTree(new int[]{0, 1, 3, 5, 7, 9, 11});
52
        System.out.println(ft.prefix(3));    // 9
53
        ft.update(2, 7);                     // a[2] -> 10
54
        System.out.println(ft.prefix(3));    // 16
55
        System.out.println(ft.rangeSum(2, 4)); // 10+5+7 = 22
56
    }
57
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.57 lines

D · Why it works and complexityO(n) build, O(log n) update, O(log n) query timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7update at index 0 — Bug trap: lowbit(0) = 0 means i never advances → infinite loop. Always keep the tree 1-based.Explore edge cases

Edge cases handled

update at index 0Bug trap: lowbit(0) = 0 means i never advances → infinite loop. Always keep the tree 1-based.
prefix(0)Loop condition i > 0 is immediately false → returns 0, the correct empty-prefix sum.
rangeSum(1, n)prefix(n) − prefix(0) = whole-array sum; prefix(0) safely returns 0.

Pitfalls

0-based indexing — lowbit(0) = 0 causes the update loop to never terminate.
Swapping the directions — climbing on query or descending on update gives wrong sums.
Storing absolute values in update instead of deltas — compute delta = new − old to set a value.
Using int for sums in Java when totals exceed 2³¹ — use long.