Fenwick Tree
An array where cell i holds the sum of a range whose length is its lowest set bit.
Fenwick Tree: Build from eight values
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)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Fenwick Tree covers these too, in the same run.