enwick Tree Data Structure with Animation - Interactive Learning
Master Fenwick Tree (BIT) - DSA Learning Platform 📊 Master Fenwick Tree Binary Indexed Tree O(log n) Queries Learn Fenwick Tree operations with interactive animations and step-by-step visualization 📖 Understanding Fenwick Tree (Binary Indexed Tree) Introduction Core Concept Operations Binary Magic Applications What is a Fenwick Tree? A Fenwick Tree (also known as Binary Indexed Tree or BIT) is a data structure that efficiently supports prefix sum queries and point updates in O(log n) time. It was invented by Peter Fenwick in 1994 as a way to efficiently compute cumulative frequencies for arithmetic coding. Unlike a simple prefix sum array that requires O(n) for updates, Fenwick Tree provides a perfect balance between query and update operations. The key insight is using binary representation of indices to determine which elements each position in the tree is responsible for summing. 🔢 Comparison with Other Methods Method Point Update Range Query Simple Array O(1) O(n) Prefix Sum Array O(n) O(1) Fenwick Tree O(log n) O(log n) Segment Tree O(log n) O(log n) 🔑 Key Characteristics O(log n) for point updates O(log n) for prefix sum queries O(n) space complexity 1-indexed array (typically) Uses binary representation tricks Simpler than Segment Tree for prefix sums Less memory than Segment Tree ⚡ Key Functions Update(i, delta): Add delta to index i Query(i): Get sum from 1 to i RangeQuery(l, r): Sum from l to r How Fenwick Tree Works Each position i in the Fenwick Tree stores the sum of elements in a specific range. The range is determined by the Lowest Set Bit (LSB) of the index. For index i, the Fenwick Tree stores the sum of elements from i - LSB(i) + 1 to i. 📊 Range Responsibility Example BIT[1]: Stores sum of A[1] BIT[2]: Stores sum of A[1..2] BIT[3]: Stores sum of A[3] BIT[4]: Stores sum of A[1..4] BIT[5]: Stores sum of A[5] BIT[6]: Stores sum of A[5..6] BIT[7]: Stores sum of A[7] BIT[8]: Stores sum of A[1..8] 📐 Core Formulas LSB(i) i & (-i) Lowest Set Bit Parent (Update) i + (i & -i) Next index to update Parent (Query) i - (i & -i) Previous index to add Range covered [i - LSB(i) + 1, i] Elements summed at i Fenwick Tree Operations 📥 Update Operation Add a value (delta) to position i: Start at index i Add delta to BIT[i] Move to next: i = i + (i & -i) Repeat until i > n Update(5, +3): 5 → 6 → 8 → 16 → ... 🔍 Query Operation (Prefix Sum) Get sum from index 1 to i: Start at index i, sum = 0 Add BIT[i] to sum Move to previous: i = i - (i & -i) Repeat until i = 0 Query(7): 7 → 6 → 4 → 0 (stop) 📊 Range Query Get sum from index l to r: RangeSum(l, r) = Query(r) - Query(l - 1) ⏱️ Time Complexity Build: O(n log n) or O(n) Point Update: O(log n) Prefix Query: O(log n) Range Query: O(log n) 💾 Space Complexity Array: O(n) Much better than Segment Tree's 4n 📝 Number of Operations Update touches at most log₂(n) indices Query sums at most log₂(n) values The Binary Magic Behind BIT The elegance of Fenwick Tree comes from clever use of binary represent...
Subject: Data Structures with Animation | Chapter: Fenwick Tree Data Structure