AlgoScope

Fenwick Tree

An array where cell i holds the sum of a range whose length is its lowest set bit.

Data structures, data structure, advancedAlso called binary indexed tree, BIT
Cell 7 holds 2. It also contributes to cell 8.03152531144510627238i
Cell 7 holds 2. It also contributes to cell 8.03152531144510627238i

Fenwick Tree: Build from eight values

Step, step 8 of 10

Cell 7 covers 7 to 7 and now holds 2. Its parent is 7 + lowbit(7) = 8, so 2 is folded in there too.

Cost

Prefix query
O(log n)
Point update
O(log n)
Build
O(n)
Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

Fenwick Tree covers these too, in the same run.