0Pricing
Coding Interview Prep · Lesson

Fenwick Tree for Prefix Sums

Point update, prefix query in log n.

Fenwick Tree for Prefix Sums is a free Coding Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

Why Prefix Arrays Break

A plain prefix-sum array answers ranges instantly, but a single update forces you to rebuild it. With many updates, that gets slow. ⏱️

Enter the Fenwick Tree

The Fenwick tree, or BIT, supports both point updates and prefix queries in O(log n). It is your go-to for dynamic running totals.

One-Indexed by Design

A Fenwick tree lives in a 1-indexed array. We use index 0 as a quiet sentinel, so all your real data starts at position 1.

tree = [0] * (n + 1)

The Magic of Lowest Set Bit

Every index covers a block of values. The block size equals i & -i, the lowest set bit of i. This one trick powers the whole tree.

lowbit = i & -i

Updating a Single Point

To add a value at position i, you jump forward by the lowbit each step, touching every block that contains i.

while i <= n:
    tree[i] += delta
    i += i & -i

Querying a Prefix Sum

To sum the first i values, you walk backward, subtracting the lowbit each step until you reach zero.

s = 0
while i > 0:
    s += tree[i]
    i -= i & -i

Both Loops Are Logarithmic

Each loop flips off one bit per iteration, so it runs at most log n times. That is why both update and query stay fast.

Range Sum from Two Prefixes

Want the sum from l to r? Take prefix(r) minus prefix(l-1), just like a static prefix array, but now updates are cheap too.

range_sum = query(r) - query(l - 1)

Building the Tree

The simplest build just calls update for each starting value. That is O(n log n) and plenty fast for most contests.

for i, v in enumerate(a, 1):
    update(i, v)

A Tiny Memory Footprint

A Fenwick tree needs just one array of size n+1. That compact footprint is part of why it is so loved in contests. 💾

When to Reach for a BIT

Pick a Fenwick tree when you interleave point updates with prefix or range sum queries. It is short to code and hard to beat.

Quick Check

Let's lock in how the loops move.

Recap: BIT Basics

You met the Fenwick tree: 1-indexed, powered by i & -i, with point update and prefix query both in O(log n). Next, we use it to count inversions. 🎯

Frequently asked questions

Is the “Fenwick Tree for Prefix Sums” lesson free?

Yes — the full text of “Fenwick Tree for Prefix Sums” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.

What will I learn in “Fenwick Tree for Prefix Sums”?

Point update, prefix query in log n. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start Coding Interview Prep?

No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Fenwick Tree for Prefix Sums” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this Coding Interview Prep lesson?

Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

  1. Fenwick Tree for Prefix Sums
  2. Inversions with a BIT
  3. Segment Tree: Build & Query
  4. Lazy Propagation for Range Updates
← Back to Coding Interview Prep