Fenwick Tree BIT

A Fenwick tree is like a clever set of partial running totals that lets you update a number and find the total up to any spot very quickly.

In this page:

What is Fenwick Tree
Prefix Query
Point Update
Uses
Complexity

Syntax

markup

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

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

What is Fenwick Tree

A Fenwick tree (Binary Indexed Tree) is a compact structure that stores partial, overlapping sums so it can answer whats the sum of the first k elements' queries and handle updates to individual elements much faster than recomputing from scratch.

Example: What is Fenwick Tree

#include <iostream>
using namespace std;
int main() {
	cout << "BIT stores partial overlapping sums to answer prefix-sum queries and handle point updates fast";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("BIT stores partial overlapping sums to answer prefix-sum queries and handle point updates fast");
	}
}

print("BIT stores partial overlapping sums to answer prefix-sum queries and handle point updates fast")

#include <stdio.h>
int main() {
	printf("BIT stores partial overlapping sums to answer prefix-sum queries and handle point updates fast");
	return 0;
}

Prefix Query

To compute a prefix sum up to some index, the BIT jumps backward through a small number of stored blocks — determined by the binary representation of the index — adding each block's value along the way, rather than summing every element one by one.

Example: Prefix Query

#include <iostream>
using namespace std;
int bit[9] = {0};
int query(int i) {
	int sum = 0;
	for (; i > 0; i -= i & (-i)) sum += bit[i];
	return sum;
}
int main() {
	bit[1]=2; bit[2]=6; bit[3]=5; bit[4]=18;
	cout << "Prefix sum up to index 4, jumping backward through blocks: " << query(4);
	return 0;
}

public class Main {
	static int[] bit = new int[9];
	static int query(int i) {
		int sum = 0;
		for (; i > 0; i -= i & (-i)) sum += bit[i];
		return sum;
	}
	public static void main(String[] args) {
		bit[1]=2; bit[2]=6; bit[3]=5; bit[4]=18;
		System.out.println("Prefix sum up to index 4, jumping backward through blocks: " + query(4));
	}
}

bit = [0]*9
bit[1], bit[2], bit[3], bit[4] = 2, 6, 5, 18
def query(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & (-i)
    return s
print("Prefix sum up to index 4, jumping backward through blocks:", query(4))

#include <stdio.h>
int bit[9] = {0};
int query(int i) {
	int sum = 0;
	for (; i > 0; i -= i & (-i)) sum += bit[i];
	return sum;
}
int main() {
	bit[1]=2; bit[2]=6; bit[3]=5; bit[4]=18;
	printf("Prefix sum up to index 4, jumping backward through blocks: %d", query(4));
	return 0;
}

Point Update

Updating a single array value only requires adjusting the handful of stored blocks whose ranges include that index, found by jumping forward through the structure using the same binary-index logic as queries but in the opposite direction.

Example: Point Update

#include <iostream>
using namespace std;
int bit[9] = {0};
void update(int i, int delta, int n) {
	for (; i <= n; i += i & (-i)) bit[i] += delta;
}
int main() {
	update(3, 5, 8);
	cout << "Updated index 3 by +5, jumping forward through the same binary-indexed blocks";
	return 0;
}

public class Main {
	static int[] bit = new int[9];
	static void update(int i, int delta, int n) {
		for (; i <= n; i += i & (-i)) bit[i] += delta;
	}
	public static void main(String[] args) {
		update(3, 5, 8);
		System.out.println("Updated index 3 by +5, jumping forward through the same binary-indexed blocks");
	}
}

bit = [0]*9
def update(i, delta, n):
    while i <= n:
        bit[i] += delta
        i += i & (-i)
update(3, 5, 8)
print("Updated index 3 by +5, jumping forward through the same binary-indexed blocks")

#include <stdio.h>
int bit[9] = {0};
void update(int i, int delta, int n) {
	for (; i <= n; i += i & (-i)) bit[i] += delta;
}
int main() {
	update(3, 5, 8);
	printf("Updated index 3 by +5, jumping forward through the same binary-indexed blocks");
	return 0;
}

Uses

Fenwick trees are especially handy whenever an array changes frequently and you repeatedly need prefix-sum-style answers — like tracking running totals, cumulative frequency counts, or 'how many elements so far are less than x' in competitive programming.

Example: Uses

#include <iostream>
using namespace std;
int main() {
	cout << "Running totals, cumulative frequency counts, 'how many elements seen so far are less than x'";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Running totals, cumulative frequency counts, 'how many elements seen so far are less than x'");
	}
}

print("Running totals, cumulative frequency counts, 'how many elements seen so far are less than x'")

#include <stdio.h>
int main() {
	printf("Running totals, cumulative frequency counts, 'how many elements seen so far are less than x'");
	return 0;
}

Complexity

Both the update and prefix-query operations only touch O(log n) blocks each, giving logarithmic time for both — a big improvement over the O(n) cost of recomputing a prefix sum directly after every change.

Example: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Fenwick tree: O(log n) update and prefix query, vs O(n) recomputing a prefix sum directly";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Fenwick tree: O(log n) update and prefix query, vs O(n) recomputing a prefix sum directly");
	}
}

print("Fenwick tree: O(log n) update and prefix query, vs O(n) recomputing a prefix sum directly")

#include <stdio.h>
int main() {
	printf("Fenwick tree: O(log n) update and prefix query, vs O(n) recomputing a prefix sum directly");
	return 0;
}

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Segment Tree Next Lesson → Disjoint Set Union DSU