concept · INFO-CS-ADS-211Fenwick Trees (Binary Indexed Trees)
A Fenwick Tree, also called a Binary Indexed Tree (BIT), is a compact data structure that efficiently calculates prefix sums and supports point updates on an array.
Explanation
Overview
A Fenwick Tree stores partial sums in an array. Each position represents a particular interval of the original data, determined by the binary representation of its index. By combining these stored values, the structure can calculate prefix sums efficiently.
How it works
The original array is represented using a separate Fenwick Tree array.; Each tree position stores the sum of a specific interval.; A prefix-sum query visits selected positions by repeatedly removing the lowest set bit from the current index.; An update modifies the relevant positions by repeatedly adding the lowest set bit.; The process uses binary indexing to avoid examining every array element.
Key concepts
Binary indexing; Lowest set bit; Prefix sums; Point updates; Partial interval sums; 1-based indexing
Time complexity
operation: Point Update; complexity: O(log n); operation: Prefix Sum; complexity: O(log n); operation: Range Sum; complexity: O(log n); operation: Build; complexity: O(n log n) with repeated updates; O(n) with an optimized construction
Example
array: 2; 4; query: Find the prefix sum from index 1 through index 4 using 1-based indexing.; calculation: 2 + 4 + 1 + 3 = 10; result: 10
Applications
Dynamic prefix sums; Range sum queries; Inversion counting; Frequency tables; Coordinate-compressed counting problems; Competitive programming
Example or application
Query
Find the prefix sum from index 1 through index 4 using 1-based indexing.
Calculation
2 + 4 + 1 + 3 = 10
Definition
A Fenwick Tree stores partial sums in an array. Each position represents a particular interval of the original data, determined by the binary representation of its index. By combining these stored values, the structure can calculate prefix sums efficiently.
How It Works
The original array is represented using a separate Fenwick Tree array.
Each tree position stores the sum of a specific interval.
A prefix-sum query visits selected positions by repeatedly removing the lowest set bit from the current index.
An update modifies the relevant positions by repeatedly adding the lowest set bit.
The process uses binary indexing to avoid examining every array element.
Key Operation
Prefix Sum
Move from index i to i - (i & -i).
Update
Move from index i to i + (i & -i).
Note
The standard Fenwick Tree implementation uses 1-based indexing.
Implementation
Code
function update(i, value):
while i <= n:
bit[i] += value
i += i & -i
function prefixSum(i):
result = 0
while i > 0:
result += bit[i]
i -= i & -i
return result
function rangeSum(left, right):
return prefixSum(right) - prefixSum(left - 1)
Time Complexity
| Operation | Complexity |
|---|
Point Update | O(log n) |
Prefix Sum | O(log n) |
Range Sum | O(log n) |
Build | O(n log n) with repeated updates; O(n) with an optimized construction |
Key Concepts
Binary indexing
Lowest set bit
Prefix sums
Point updates
Partial interval sums
1-based indexing
Advantages
Uses less memory than a typical Segment Tree.
Supports efficient prefix-sum queries and point updates.
Has a relatively simple implementation.
Can be extended to support additional operations and counting problems.
Limitations
Standard Fenwick Trees are less flexible than Segment Trees.
Range updates and other advanced operations require additional techniques.
The standard sum implementation assumes suitable additive values.
Indexing errors are common when mixing zero-based and one-based arrays.
Related Topics
Segment Trees
Prefix Sums
Sparse Tables
Binary Representation
Range Query Algorithms
Practice Questions
| Question | Answer |
|---|
What is another name for a Fenwick Tree? | Binary Indexed Tree (BIT). |
What does a standard Fenwick Tree efficiently calculate? | Prefix sums and, through subtraction, range sums. |
What is the time complexity of a prefix-sum query? | O(log n). |
Learning Objectives
Explain the central idea and purpose of fenwick trees (binary indexed trees).
Identify the assumptions, inputs, and conditions relevant to fenwick trees (binary indexed trees).
Evaluate an application of fenwick trees (binary indexed trees) for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
Suggest a correction or source · More in Algorithms & Data Structures