RavensMove

Fenwick Tree Visualizer

Build a Binary Indexed Tree, inspect each one-based coverage range, run prefix-sum jumps, and preview point updates.

Values
8
BIT slots
8
Lowbit
1
Sum
11

Fenwick input

The input is zero-based. Fenwick tree slots are shown one-based.

Range query

Point update

Step controls

Step 1 of 6: Start range sum query [2, 6] as prefix(6) - prefix(1).

Fenwick tree slots

Start range sum query [2, 6] as prefix(6) - prefix(1).

Active Right/update Left prefix
tree[i]
lowbit
covers array indexes
sum
[1]
1
[0, 0] 3
3
[2]
2
[0, 1] 3 + 2
5
[3]
1
[2, 2] -1
-1
[4]
4
[0, 3] 3 + 2 + -1 + 6
10
[5]
1
[4, 4] 5
5
[6]
2
[4, 5] 5 + 4
9
[7]
1
[6, 6] -3
-3
[8]
8
[0, 7] 3 + 2 + -1 + 6 + 5 + 4 + -3 + 7
23

Array view

0
3
1
2
2
-1
3
6
4
5
5
4
6
-3
7
7

Query summary

range = [2, 6]
right prefix = 0
left prefix = 0
sum = 11

Trace

Step 1. Start range sum query [2, 6] as prefix(6) - prefix(1).
Step 2. Right prefix takes tree[7] = -3, then jumps to 6.
Step 3. Right prefix takes tree[6] = 9, then jumps to 4.
Step 4. Right prefix takes tree[4] = 10, then jumps to 0.
Step 5. Left prefix takes tree[2] = 5, then jumps to 0.
Step 6. Range sum [2, 6] = 16 - 5 = 11.

What is a Fenwick Tree Visualizer?

A Fenwick tree visualizer shows how a Binary Indexed Tree stores partial sums in a compact array.

This tool builds the tree array from your input values, shows the range covered by each Fenwick index, and traces prefix sums using index -= lowbit(index). It also previews point updates using index += lowbit(index).

For the full cluster of related pages, browse the Data Structure Visualizers hub.

How to use this Fenwick tree visualizer

  • Paste an array of whole numbers.
  • Choose a left and right index for a range sum query.
  • Run the query to see prefix(right) - prefix(left - 1).
  • Choose an index and new value to preview the point update path.
  • Compare each Fenwick tree slot with the original array range it covers.

Fenwick tree vs segment tree

A Fenwick tree is smaller and often simpler than a segment tree for prefix sums and point updates. It stores sums in one array and uses the least significant set bit to decide which ranges are covered.

Use the Segment Tree Visualizer when you want to compare this compact structure with a tree-shaped range-query structure.

For static range minimum and maximum queries, use the Sparse Table Visualizer.

Frequently Asked Questions

What is lowbit in a Fenwick tree?
`lowbit(index)` is the least significant set bit of a one-based index. It tells the visualizer how wide the covered range is.
How does a Fenwick tree answer range sums?
It computes two prefix sums, one ending at the right index and one ending before the left index, then subtracts them.
What does a Fenwick point update change?
A point update changes the selected array value and every Fenwick tree slot whose covered range includes that index.
Is a Fenwick tree zero-based or one-based?
The input array is shown with zero-based indexes, while the Fenwick tree itself uses one-based indexes.

Related tools

Binary Search Tree Visualizer Visualize binary search tree operations online. Paste an insertion-order array, render the BST, and run search, delete, insert, and traversal steps.Binary Search Visualizer Visualize binary search online. Paste a sorted array, choose exact search or lower bound, and inspect low, high, mid, comparisons, and result index.Prefix Sum Visualizer Visualize prefix sum arrays online. Paste values, build cumulative sums step by step, choose a range, and inspect how range sum queries work.