Fenwick Tree

Introduction

Fenwick Tree, aka Binary Indexed Tree (BIT): data structure for cumulative frequency tables. Supports prefix sum queries and updates in O(log n) time. Space-efficient alternative to segment trees. Widely used in competitive programming, database indexing, and statistical computations.

"The Fenwick Tree offers a simple yet powerful tool for dynamic prefix sums, enabling efficient updates and queries." -- Peter Fenwick

History and Origin

Inventor and Naming

Developed by Peter Fenwick in 1994. Originally published in "A New Data Structure for Cumulative Frequency Tables". Named Fenwick Tree or Binary Indexed Tree due to indexing technique.

Motivation

Need for efficient update and prefix sum query beyond naive O(n) methods. Fenwick proposed a structure with O(log n) operations, less memory than segment trees.

Evolution

Extended for multidimensional queries, range updates, and various applications. Popularized in algorithm competitions and research.

Core Concept and Definition

Prefix Sum Problem

Compute sum of elements from start to given index. Naive: O(n) per query. Fenwick Tree reduces to O(log n).

Binary Indexed Representation

Uses binary representation of indices to store partial sums. Each node covers a range defined by least significant bit (LSB).

Fundamental Principle

Each node stores cumulative frequency of a specific segment. Query aggregates nodes covering prefix. Update modifies affected nodes.

Data Structure and Representation

Array-Based Implementation

Fenwick Tree stored as 1D array 'fenwicks' of size n+1 (1-indexed). Index 0 unused for simplicity.

Indexing Scheme

Node at index i covers range [i - LSB(i) + 1, i]. LSB(i) = i & (-i). Enables jumping between nodes efficiently.

Memory Layout

Compact structure uses O(n) space. No explicit tree nodes or pointers; implicit tree via indices.

Operations and Algorithms

Prefix Sum Query

Calculate sum of elements from index 1 to i. Algorithm: sum nodes while decrementing i by LSB(i).

Update Operation

Add delta to element at index i. Algorithm: update all nodes covering i by incrementing i by LSB(i).

Range Sum Query

Sum between indices l and r: prefix_sum(r) - prefix_sum(l-1). Supports dynamic arrays.

function prefix_sum(i): result = 0 while i > 0: result += fenwicks[i] i -= i & (-i) return resultfunction update(i, delta): while i <= n: fenwicks[i] += delta i += i & (-i)

Time and Space Complexity

Time Complexity

Both update and prefix sum queries run in O(log n) time due to binary index traversal.

Space Complexity

Uses O(n) space for fenwicks array storing partial sums.

Comparison to Alternatives

Faster and simpler than segment trees for prefix sums. Segment trees provide more flexibility but with higher overhead.

Applications

Frequency Counting

Dynamic counting of occurrences in data streams or arrays.

Inversion Count

Used to compute number of inversions in O(n log n) time.

Range Queries in Databases

Optimizing queries involving cumulative sums and updates.

Competitive Programming

Standard tool for range and frequency query problems.

Comparison with Other Structures

Fenwick Tree vs Segment Tree

Fenwick: simpler, less memory, prefix sums only. Segment: flexible, supports various aggregates, more complex.

Fenwick Tree vs Binary Search Tree

Fenwick specialized for prefix sums; BST for ordered data with dynamic insertions/deletions.

Fenwick Tree vs Sparse Table

Fenwick supports updates; Sparse Table supports static range queries in O(1).

Implementation Details

Initialization

Fenwicks array initialized with zeros, size n+1. 1-based indexing mandatory for clarity.

Building from Array

Build Fenwick Tree in O(n log n) by updating each element. Alternative O(n) build possible with advanced methods.

Code Snippet

function build(arr, n): fenwicks = array of size n+1 initialized to 0 for i in 1 to n: update(i, arr[i])

Optimizations and Variants

Range Updates and Point Queries

Dual Fenwick Trees enable range increments with point queries by maintaining two trees.

2D Fenwick Tree

Extension for two-dimensional arrays to answer prefix sums on 2D grids.

Space Optimization

In-place Fenwick Trees or compressed Fenwicks for memory-critical applications.

Limitations and Constraints

Limited Query Types

Supports prefix sums and point updates; not suitable for arbitrary range queries without modifications.

Indexing Constraints

1-based indexing mandatory; zero indexing requires offset adjustments.

Data Type Restrictions

Works best with commutative operations like addition; complex aggregates need alternate structures.

Examples and Use Cases

Example: Frequency Array

Count frequencies of elements dynamically; query cumulative counts efficiently.

Example: Inversion Count

Calculate number of inversions in an array for sorting analysis.

Sample Code

n = length of arrayfenwicks = array of size n+1 initialized to 0function update(i, delta): while i <= n: fenwicks[i] += delta i += i & (-i)function prefix_sum(i): result = 0 while i > 0: result += fenwicks[i] i -= i & (-i) return result# To get sum in [l, r]:sum = prefix_sum(r) - prefix_sum(l-1)

References

• Fenwick, P. M. "A New Data Structure for Cumulative Frequency Tables." Software: Practice and Experience, vol. 24, no. 3, 1994, pp. 327-336.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. "Introduction to Algorithms." MIT Press, 3rd Edition, 2009, pp. 240-245.
• Bentley, J. L. "Programming Pearls: Algorithm Design Techniques." Communications of the ACM, vol. 27, no. 9, 1984, pp. 865-873.
• Gusfield, D. "Algorithms on Strings, Trees and Sequences." Cambridge University Press, 1997, pp. 80-85.
• Fenwick Tree Tutorials and Applications. Competitive Programming Handbook, Antti Laaksonen, 2017.