Skip to content
Hello Python

Trace Fenwick-Tree Prefixes

Practice ExerciseAdvancedHardArrayFenwick Tree

Checking your account…

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

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

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.

Starter code

def fenwick_tree_trace(values, operations):
    pass
Test cases

prefix-add-range

{
  "args": [
    [
      2,
      1,
      5,
      3
    ],
    [
      [
        "prefix",
        2
      ],
      [
        "add",
        1,
        4
      ],
      [
        "range",
        1,
        3
      ]
    ]
  ]
}

Expected: [8,13]

left-boundary

{
  "args": [
    [
      4,
      6
    ],
    [
      [
        "range",
        0,
        0
      ],
      [
        "prefix",
        1
      ]
    ]
  ]
}

Expected: [4,10]

Wizard outline
  1. Step 1: Build and read a prefix

    Populate a one-indexed Fenwick tree and accumulate a prefix by removing its low bit. A prefix query reveals both update and traversal directions in the compact tree.

  2. Step 2: Apply a point delta

    Reuse the add helper so a later prefix includes the requested delta. A runtime add follows the identical ancestor-update path as construction.

  3. Step 3: Subtract two prefixes for a range

    Return an inclusive range sum as prefix(right) minus prefix(left - 1). Prefix subtraction converts the structure into an arbitrary inclusive range tool.

Footguns and prerequisites
  • Fenwick storage is one-indexed even when the public array is zero-indexed.
  • A range sum needs prefix(right) minus prefix(left - 1), not prefix(left).
  • trees and graphs
Reviewed references
Recommended approach and implementation

Build one-indexed Fenwick aggregates, move by low bits for updates and prefix queries, and subtract prefix boundaries for ranges.

Why it works: Each add updates exactly the stored intervals containing its point. Prefix traversal partitions [0, index] into disjoint stored intervals, so its sum is exact; subtracting the prefix before left leaves exactly the inclusive requested range.

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