Efficient data aggregation with Fenwick trees
summary
Fenwick tree stores cumulative blocks inside the original array so it gives no extra memory while supporting O(log n) updates and queries; building the in-place index from a raw array runs in linear time. Reading a single recovered element costs more — measured as about ~4x slowdown vs plain array in-cache and closer to 2x when memory is larger than cache — and updates apply as deltas along the index in logarithmic time.
AI-written summary · about
chapters (7)
- 0:00Intro
- 0:48The Problem
- 1:17Obvious Solutions
- 2:33Build an Index
- 4:20Skimping on Memory
- 8:10Usage: Updates
- 11:12Fenwick Trees
related talks
01h 09mThere's Treasure Everywhere
48mDesign of data-intensive applications
26mStorage Gardening: Using a Virtualization Layer for Efficient Defragmentation in the WAFL
42mAdventures in Efficiency and Performance
01h 16mHow do to do research with Systems Researchers
16mMemory-Efficient Fixpoint Computation
01h 04mHow We Build Firebolt
34mFast Code Without Breaking Things