What Is a Fenwick Tree? Prefix Sums With No Update Penalty

You have an array of numbers. Two operations: query the sum of any range, update any single element. How fast can you make both?

Naive array: point update in O(1), range query in O(n). Prefix sum array: range query in O(1), but now every update costs O(n) because you recompute everything downstream. Pick your poison.

Congratulations, you've discovered the classic tradeoff. Tuesday for most engineers.

The Fenwick tree (also called a binary indexed tree, or BIT), invented by Peter Fenwick in 1994, refuses to pick. Both operations run in O(log n), space is O(n), and the whole thing fits in about fifteen lines of code.

The Problem Prefix Sums Can't Solve

Prefix sums are elegant for static arrays. Build them once in O(n), and any range sum [l, r] is prefix[r] - prefix[l-1]. Constant time, dead simple.

If your array never changes, stop reading. Go enjoy your O(1) queries and your uncomplicated life.

The moment you need to update index i, you have to recalculate every prefix entry from i to n. That's O(n) per update. For read-heavy workloads it's fine. For anything with frequent mutations, it falls apart completely.

The Fenwick tree's core insight: you don't need a complete prefix sum array. You only need enough partial sums that you can reconstruct any prefix quickly using a small number of lookups.

Fourteen lookups at most, for an array of 16,384 elements. Because log₂(16384) = 14. That's the whole magic trick.

Each Index Owns a Range

Instead of storing raw array values, you maintain a parallel array called tree where each position i holds the sum of a specific range ending at i.

The length of that range is determined by one thing: the lowest set bit of i.

Take index 6. In binary, 6 is 110. The lowest set bit is at position 1 (value 2). So tree[6] stores the sum of 2 elements: arr[5] + arr[6].

Take index 8. In binary, 8 is 1000. The lowest set bit is at position 3 (value 8). So tree[8] stores the sum of 8 elements: arr[1] through arr[8].

Take index 7. In binary, 7 is 0111. The lowest set bit is at position 0 (value 1). So tree[7] stores just arr[7]. Index 7 is pulling its own weight and nobody else's.

These responsibility ranges tile the array without overlap. Any prefix sum can be reconstructed by summing a small set of them. Any update touches only the indexes whose ranges cover the changed position.

The wider the bar, the more an index is responsible for. Index 8 is carrying the whole team.

The Bit Trick: lowbit(i) = i & (-i)

Here is the most important line of code in the entire data structure:

lowbit = i & (-i)

That's it. One expression. Everything else is just walking around using this value.

Why does this work? In two's complement, -i is the bitwise NOT of i plus 1. That +1 propagates a carry through all the trailing zeros, flipping them to ones and then stopping at the first set bit, which flips to zero. When you AND -i with the original i, everything above the lowest set bit cancels out (one has 0, the other has 1 at each position), and everything below is zero. You're left with exactly the lowest set bit.

i        =  6  →  0 0 0 0 0 1 1 0
-i       = -6  →  1 1 1 1 1 0 1 0  (two's complement)
i & (-i) =  2  →  0 0 0 0 0 0 1 0

Peter Fenwick published this in 1994 and engineers have been using it to look clever ever since. This single expression is the entire implementation secret. Everything else is just walking up or down the index space using this value.

How Queries Work: Walk Toward Zero

To get the prefix sum from index 1 through i, start at i and repeatedly subtract lowbit(i) until you reach 0. At each step, add tree[i] to the running total.

def query(i):
    total = 0
    while i > 0:
        total += tree[i]
        i -= i & (-i)
    return total

Trace through query(7) on an 8-element tree:

• i = 7 (111), lowbit = 1. Add tree[7]. Move to i = 6.
• i = 6 (110), lowbit = 2. Add tree[6]. Move to i = 4.
• i = 4 (100), lowbit = 4. Add tree[4]. Move to i = 0.
• Done. Three additions instead of seven.

This works because tree[4] already holds arr[1..4], tree[6] holds arr[5..6], and tree[7] holds arr[7]. They tile perfectly with no gaps and no overlaps. No element gets double-counted. No element gets missed.

How Updates Work: Walk Toward n

To add delta to position i, update tree[i], then move to i + lowbit(i) and update again, continuing until you're past n.

def update(i, delta):
    while i <= n:
        tree[i] += delta
        i += i & (-i)

Trace through update(5, +1) on an 8-element tree:

• i = 5 (101), lowbit = 1. Update tree[5]. Move to i = 6.
• i = 6 (110), lowbit = 2. Update tree[6]. Move to i = 8.
• i = 8 (1000), lowbit = 8. Update tree[8]. Move to i = 16.
• 16 > 8, done.

You're touching every index whose responsibility range covers position 5, propagating the change upward to all ancestors. Index 5 owns [5,5], index 6 owns [5,6], and index 8 owns [1,8]. All three include position 5, so all three need updating. The ones that don't cover position 5 get left alone.

A Concrete Worked Example

Take the array [3, 2, -1, 6, 5, 4] (1-indexed). Build the Fenwick tree by calling update(i, arr[i]) for each position.

i	Binary	lowbit	Responsibility	tree[i]
1	001	1	[1, 1]	3
2	010	2	[1, 2]	5
3	011	1	[3, 3]	-1
4	100	4	[1, 4]	10
5	101	1	[5, 5]	5
6	110	2	[5, 6]	9

Now query the range sum [2, 5] using query(5) - query(1):

query(5): i=5, add tree[5]=5, move to i=4. i=4, add tree[4]=10, move to i=0. Result: 15.

query(1): i=1, add tree[1]=3, move to i=0. Result: 3.

Range sum [2, 5] = 15 - 3 = 12. Check: 2 + (-1) + 6 + 5 = 12. Correct.

Now update arr[3] from -1 to 2 (delta = +3). Call update(3, 3):

• i=3: tree[3] becomes 2. Move to i=4.
• i=4: tree[4] becomes 13. Move to i=8.
• 8 > 6, done.

Run query(5) - query(1) again: tree[4]=13, tree[5]=5, prefix(5)=18. Subtract prefix(1)=3. Range [2,5] = 15. Check: 2 + 2 + 6 + 5 = 15. Correct.

Time and Space

Both query and update traverse at most O(log n) nodes. In the query direction, each step strips the lowest set bit, which strictly decreases i. In the update direction, each step sets the lowest set bit at a higher position, which strictly increases i. A number with at most log₂(n) bits can only do log₂(n) such steps. That's the proof.

Operation	Time	Space
Build	O(n log n)	O(n)
Point update	O(log n)	O(1)
Prefix query	O(log n)	O(1)
Range query	O(log n)	O(1)

There's also an O(n) build. Initialize tree[i] = arr[i], then for each i from 1 to n, add tree[i] to tree[i + lowbit(i)] if that index is in bounds. This propagates each value exactly once to the right parent nodes.

The space is a single flat array of size n+1. No pointers, no node structs, no heap allocation beyond that one array.

Compare that to a segment tree: 4n space in the worst case, recursive or iterative tree traversal, and significantly more code. When you only need range sum with point updates, the Fenwick tree is the right call.

One Structure, Every Language

The implementation is identical across languages: a 1-indexed array, the i & (-i) trick, and two while loops.

Python 3

class FenwickTree:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i: int, delta: int) -> None:
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i: int) -> int:
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)
        return total

    def range_query(self, left: int, right: int) -> int:
        return self.query(right) - self.query(left - 1)

Python 2

class FenwickTree(object):
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)
        return total

    def range_query(self, left, right):
        return self.query(right) - self.query(left - 1)

JavaScript

class FenwickTree {
  constructor(n) {
    this.n = n;
    this.tree = new Array(n + 1).fill(0);
  }

  update(i, delta) {
    while (i <= this.n) {
      this.tree[i] += delta;
      i += i & (-i);
    }
  }

  query(i) {
    let total = 0;
    while (i > 0) {
      total += this.tree[i];
      i -= i & (-i);
    }
    return total;
  }

  rangeQuery(left, right) {
    return this.query(right) - this.query(left - 1);
  }
}

TypeScript

class FenwickTree {
  private n: number;
  private tree: number[];

  constructor(n: number) {
    this.n = n;
    this.tree = new Array(n + 1).fill(0);
  }

  update(i: number, delta: number): void {
    while (i <= this.n) {
      this.tree[i] += delta;
      i += i & -i;
    }
  }

  query(i: number): number {
    let total = 0;
    while (i > 0) {
      total += this.tree[i];
      i -= i & -i;
    }
    return total;
  }

  rangeQuery(left: number, right: number): number {
    return this.query(right) - this.query(left - 1);
  }
}

Java

class FenwickTree {
    private int n;
    private int[] tree;

    public FenwickTree(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }

    public void update(int i, int delta) {
        while (i <= n) {
            tree[i] += delta;
            i += i & (-i);
        }
    }

    public int query(int i) {
        int total = 0;
        while (i > 0) {
            total += tree[i];
            i -= i & (-i);
        }
        return total;
    }

    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
}

C++

class FenwickTree {
private:
    int n;
    std::vector<int> tree;

public:
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    void update(int i, int delta) {
        for (; i <= n; i += i & (-i))
            tree[i] += delta;
    }

    int query(int i) {
        int total = 0;
        for (; i > 0; i -= i & (-i))
            total += tree[i];
        return total;
    }

    int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
};

C

#define MAX_N 100001

int tree[MAX_N];
int n;

void update(int i, int delta) {
    for (; i <= n; i += i & (-i))
        tree[i] += delta;
}

int query(int i) {
    int total = 0;
    for (; i > 0; i -= i & (-i))
        total += tree[i];
    return total;
}

int range_query(int left, int right) {
    return query(right) - query(left - 1);
}

Go

type FenwickTree struct {
    n    int
    tree []int
}

func NewFenwickTree(n int) *FenwickTree {
    return &FenwickTree{n: n, tree: make([]int, n+1)}
}

func (ft *FenwickTree) Update(i, delta int) {
    for ; i <= ft.n; i += i & (-i) {
        ft.tree[i] += delta
    }
}

func (ft *FenwickTree) Query(i int) int {
    total := 0
    for ; i > 0; i -= i & (-i) {
        total += ft.tree[i]
    }
    return total
}

func (ft *FenwickTree) RangeQuery(left, right int) int {
    return ft.Query(right) - ft.Query(left-1)
}

Rust

struct FenwickTree {
    n: usize,
    tree: Vec<i64>,
}

impl FenwickTree {
    fn new(n: usize) -> Self {
        FenwickTree { n, tree: vec![0; n + 1] }
    }

    fn update(&mut self, mut i: usize, delta: i64) {
        while i <= self.n {
            self.tree[i] += delta;
            i += i & i.wrapping_neg();
        }
    }

    fn query(&self, mut i: usize) -> i64 {
        let mut total = 0;
        while i > 0 {
            total += self.tree[i];
            i -= i & i.wrapping_neg();
        }
        total
    }

    fn range_query(&self, left: usize, right: usize) -> i64 {
        self.query(right) - self.query(left - 1)
    }
}

Rust uses wrapping_neg() because negating an unsigned integer wraps by default in release mode, and this makes the intent explicit. Rust will not let you be sneaky about arithmetic. You know this about Rust.

Swift

class FenwickTree {
    private var n: Int
    private var tree: [Int]

    init(_ n: Int) {
        self.n = n
        self.tree = Array(repeating: 0, count: n + 1)
    }

    func update(_ i: Int, _ delta: Int) {
        var index = i
        while index <= n {
            tree[index] += delta
            index += index & (-index)
        }
    }

    func query(_ i: Int) -> Int {
        var total = 0
        var index = i
        while index > 0 {
            total += tree[index]
            index -= index & (-index)
        }
        return total
    }

    func rangeQuery(_ left: Int, _ right: Int) -> Int {
        return query(right) - query(left - 1)
    }
}

Kotlin

class FenwickTree(private val n: Int) {
    private val tree = IntArray(n + 1)

    fun update(i: Int, delta: Int) {
        var index = i
        while (index <= n) {
            tree[index] += delta
            index += index and (-index)
        }
    }

    fun query(i: Int): Int {
        var total = 0
        var index = i
        while (index > 0) {
            total += tree[index]
            index -= index and (-index)
        }
        return total
    }

    fun rangeQuery(left: Int, right: Int): Int {
        return query(right) - query(left - 1)
    }
}

C#

public class FenwickTree {
    private int n;
    private int[] tree;

    public FenwickTree(int n) {
        this.n = n;
        tree = new int[n + 1];
    }

    public void Update(int i, int delta) {
        while (i <= n) {
            tree[i] += delta;
            i += i & (-i);
        }
    }

    public int Query(int i) {
        int total = 0;
        while (i > 0) {
            total += tree[i];
            i -= i & (-i);
        }
        return total;
    }

    public int RangeQuery(int left, int right) {
        return Query(right) - Query(left - 1);
    }
}

Ruby

class FenwickTree
  def initialize(n)
    @n = n
    @tree = Array.new(n + 1, 0)
  end

  def update(i, delta)
    while i <= @n
      @tree[i] += delta
      i += i & (-i)
    end
  end

  def query(i)
    total = 0
    while i > 0
      total += @tree[i]
      i -= i & (-i)
    end
    total
  end

  def range_query(left, right)
    query(right) - query(left - 1)
  end
end

PHP

class FenwickTree {
    private int $n;
    private array $tree;

    public function __construct(int $n) {
        $this->n = $n;
        $this->tree = array_fill(0, $n + 1, 0);
    }

    public function update(int $i, int $delta): void {
        while ($i <= $this->n) {
            $this->tree[$i] += $delta;
            $i += $i & (-$i);
        }
    }

    public function query(int $i): int {
        $total = 0;
        while ($i > 0) {
            $total += $this->tree[$i];
            $i -= $i & (-$i);
        }
        return $total;
    }

    public function rangeQuery(int $left, int $right): int {
        return $this->query($right) - $this->query($left - 1);
    }
}

Where Fenwick Trees Show Up in Interviews

LeetCode 307: Range Sum Query, Mutable. The canonical problem. Array updates and prefix sum queries, exactly what this structure was designed for. A segment tree works too, but reaching for a Fenwick tree here signals that you know the right tool and aren't just reaching for the biggest hammer.

LeetCode 315: Count of Smaller Numbers After Self. Coordinate-compress the values to [1, n], sweep right-to-left, and for each element query how many smaller values have already been inserted. Each operation is O(log n), total O(n log n).

LeetCode 493: Reverse Pairs. Same idea: Fenwick tree over compressed coordinates. Often cleaner than the merge sort approach once you see the pattern.

Counting inversions. A pair (i, j) where i < j but arr[i] > arr[j]. Sweep left to right, query the count of larger values already inserted. O(n log n).

2D Fenwick tree. Extend to two dimensions for 2D range sums. Each axis uses its own lowbit traversal. Complexity becomes O(log m · log n) per operation. Two while loops become four. Still fits on a whiteboard.

The pattern: you have a sequence of values, need to count or sum them with modifications, ordered by position or value. When you see that shape, you reach for this.

Fenwick Tree vs Segment Tree: When to Reach for Which

This comparison comes up in interviews, sometimes explicitly.

Criterion	Fenwick Tree	Segment Tree
Code length	~15 lines	~40 lines
Space	O(n)	O(4n)
Point update	O(log n)	O(log n)
Range query	O(log n)	O(log n)
Range update	Needs difference array trick	Built in with lazy propagation
Range min/max	Not directly supported	Supported
Aggregate types	Invertible only (sum, XOR, product)	Any associative function

If you only need range sum with point updates, the Fenwick tree is strictly better: simpler code, less memory, same asymptotic performance. For range minimum queries, range maximum queries, or range updates with lazy propagation, use a segment tree.

In interviews, the Fenwick tree is often the intended solution for problems involving prefix sums over a mutable array. If you reach for a segment tree and write 40 lines when 15 would do, that's not wrong. But the interviewer notices, and they are writing something down.

If you want to see both structures built and compared side by side, the segment tree guide covers lazy propagation and when the extra complexity pays off. For the prefix sum patterns that typically precede learning Fenwick trees, prefix sum problems is a good starting point.

Practice the Explanation Out Loud

Reading a Fenwick tree is one thing. Explaining why i += i & (-i) propagates to exactly the right parent nodes, while under interview pressure, in real time, to a human who is evaluating you, is another thing entirely.

The gap between understanding a solution and narrating it under time pressure is where most candidates lose points. SpaceComplexity runs voice-based DSA mock interviews where you explain structures like this aloud, not just code them. The feedback tells you where your explanation breaks down before it costs you an offer.

Further Reading

• Binary Indexed Tree (Fenwick Tree), Wikipedia
• Binary Indexed Tree or Fenwick Tree, GeeksforGeeks
• Fenwick Tree, CP-Algorithms
• Range Sum Query, Mutable (LeetCode 307)
• Peter Fenwick, "A New Data Structure for Cumulative Frequency Tables", 1994, Software: Practice and Experience