Skip to content
Hello Python
Data Structure1 Practice2 Interview

Fenwick Tree

Compact indexed tree supporting logarithmic prefix aggregates and point updates. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Fenwick Tree when the prompt's constraints and required operations match this shape: Compact indexed tree supporting logarithmic prefix aggregates and point updates.

Pybit studies a professional Fenwick Tree interview workspace with precise technical objects.
On this page · Each Index Owns a Suffix Block

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Fenwick Tree Code Labs

Each Index Owns a Suffix Block

Fenwick trees use a one-based array. Slot i owns the suffix block ending at i whose length is i & -i. For example, slot 6 owns positions 5 through 6, while slot 8 owns positions 1 through 8. These overlapping blocks let a prefix decompose into only O(log n) pieces.

Map Fenwick Block Ownership

Reference
def fenwick_block_ranges(n):
    return [[index - (index & -index) + 1, index] for index in range(1, n + 1)]
Practice

Implement fenwick_block_ranges(n). Return [left, right] one-based inclusive ranges owned by Fenwick slots 1 through n.

Public tests

  • Map lowbit blocks

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Move with the Lowest Set Bit

lowbit = i & -i encodes both directions. A prefix query subtracts lowbit to remove the block it just consumed. A point update adds lowbit to visit every larger block containing that position. Keep public indexes zero-based if the prompt uses them, but convert once at the boundary.

Update and Query Prefixes

A range sum [left, right] is prefix(right) - prefix(left - 1). The left - 1 boundary is essential; prefix(-1) should contribute zero. Each query or update changes one bit per step, so it takes O(log n).

Trace Fenwick-Tree Prefixes

Reference
def fenwick_tree_trace(values, operations):
    tree = [0] * (len(values) + 1)
    def add(index, delta):
        index += 1
        while index < len(tree):
            tree[index] += delta
            index += index & -index
    def prefix(index):
        index += 1
        total = 0
        while index > 0:
            total += tree[index]
            index -= index & -index
        return total
    for index, value in enumerate(values):
        add(index, value)
    results = []
    for operation in operations:
        if operation[0] == "prefix":
            results.append(prefix(operation[1]))
        elif operation[0] == "add":
            add(operation[1], operation[2])
        elif operation[0] == "range":
            results.append(prefix(operation[2]) - prefix(operation[1] - 1))
    return results
Practice

Implement fenwick_tree_trace(values, operations). Operations are ["prefix", index], ["add", index, delta], or ["range", left, right], with inclusive indexes. Return one number for each prefix or range query and do not mutate values.

Public tests

  • Verify Trace Fenwick-Tree Prefixes behavior

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Fenwick or Segment Tree

Choose Fenwick for point updates plus prefix-friendly invertible aggregates such as sums: it is compact and short to implement. Choose a segment tree for arbitrary associative range combines, explicit interval ownership, or extensions such as lazy propagation. If there are no updates, precomputed prefix sums are simpler.

Explain It in an Interview

Say: “Tree slot i stores the aggregate for the block ending at i with length lowbit(i). Queries remove owned blocks; updates climb to every owner.” Trace one prefix in binary, then state O(log n) per operation and O(n) space. See the Python list reference(opens in a new tab) for the underlying array behavior.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Fenwick Tree itself is taught as an interview abstraction.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Core Fenwick Tree workflowO((n + m) log n)O((n + m) log n)Build one-indexed Fenwick aggregates, move by low bits for updates and prefix queries, and subtract prefix boundaries for ranges.

Space

O(n) for the demonstrated Fenwick Tree workflow.

Assumptions

  • Tree indexing provides logarithmic updates and prefix or interval queries after linear construction.
  • The bound counts the operations in Trace Fenwick-Tree Prefixes and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

  1. State the precise Fenwick Tree invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Use index low bits to move through Fenwick ancestors. This remains true after every accepted operation.
  3. Derive inclusive range sums from two prefix sums. This remains true after every accepted operation.

When To Use Or Avoid Fenwick Tree

Use It When

  • Use Fenwick Tree when its representation directly supports the prompt's repeated query or update.
  • Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

  • Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
  • Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Fenwick Tree invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def fenwick_tree_trace(values, operations):
    pass

Use instead

def fenwick_tree_trace(values, operations):
    tree = [0] * (len(values) + 1)
    def add(index, delta):
        index += 1
        while index < len(tree):
            tree[index] += delta
            index += index & -index
    def prefix(index):
        index += 1
        total = 0
        while index > 0:
            total += tree[index]
            index -= index & -index
        return total
    for index, value in enumerate(values):
        add(index, value)
    results = []
    for operation in operations:
        if operation[0] == "prefix":
            results.append(prefix(operation[1]))
        elif operation[0] == "add":
            add(operation[1], operation[2])
        elif operation[0] == "range":
            results.append(prefix(operation[2]) - prefix(operation[1] - 1))
    return results

Where you will hit this: Trace Fenwick-Tree Prefixes(opens in a new tab)

Breaking the central invariant

Uses prefix(left) instead of prefix(left - 1), incorrectly excluding the first value in every range.

Prevent it: Keep this invariant visible while editing: State the precise Fenwick Tree invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def fenwick_tree_trace(values, operations):
    results = []
    for operation in operations:
        if operation[0] == "range":
            results.append(sum(values[operation[1] + 1:operation[2] + 1]))
        elif operation[0] == "prefix":
            results.append(sum(values[:operation[1] + 1]))
    return results

Use instead

def fenwick_tree_trace(values, operations):
    tree = [0] * (len(values) + 1)
    def add(index, delta):
        index += 1
        while index < len(tree):
            tree[index] += delta
            index += index & -index
    def prefix(index):
        index += 1
        total = 0
        while index > 0:
            total += tree[index]
            index -= index & -index
        return total
    for index, value in enumerate(values):
        add(index, value)
    results = []
    for operation in operations:
        if operation[0] == "prefix":
            results.append(prefix(operation[1]))
        elif operation[0] == "add":
            add(operation[1], operation[2])
        elif operation[0] == "range":
            results.append(prefix(operation[2]) - prefix(operation[1] - 1))
    return results

Where you will hit this: Trace Fenwick-Tree Prefixes(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O((n + m) log n).

Avoid

def fenwick_tree_trace(values, operations):
    results = []
    for operation in operations:
        if operation[0] == "range":
            results.append(sum(values[operation[1] + 1:operation[2] + 1]))
        elif operation[0] == "prefix":
            results.append(sum(values[:operation[1] + 1]))
    return results

Use instead

def fenwick_tree_trace(values, operations):
    tree = [0] * (len(values) + 1)
    def add(index, delta):
        index += 1
        while index < len(tree):
            tree[index] += delta
            index += index & -index
    def prefix(index):
        index += 1
        total = 0
        while index > 0:
            total += tree[index]
            index -= index & -index
        return total
    for index, value in enumerate(values):
        add(index, value)
    results = []
    for operation in operations:
        if operation[0] == "prefix":
            results.append(prefix(operation[1]))
        elif operation[0] == "add":
            add(operation[1], operation[2])
        elif operation[0] == "range":
            results.append(prefix(operation[2]) - prefix(operation[1] - 1))
    return results

Where you will hit this: Map Sum Pairs(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.