🌿Fenwick Tree

NEW

Also known as: Binary Indexed Tree

A tree-like array structure that supports prefix sums and point updates in logarithmic time.

DESCRIPTION

A Fenwick Tree (Binary Indexed Tree) stores cumulative frequencies or sums in a compact array using binary decomposition of indices. It supports O(log n) point updates and prefix queries with low constant factors and memory overhead. It’s ideal for frequency counting, inversion counting, and dynamic cumulative sums. Unlike Segment Trees, BITs are simpler and more cache-friendly but less flexible for complex range operations. Extensions enable range updates with clever transformations.

ALTERNATIVE DEFINITIONS

Wikipedia

In computing, a Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

Focuses on efficient prefix sums and updates in numeric tables.

Source

CP-Algorithms

Fenwick tree is a data structure that can efficiently update elements and calculate prefix sums in O(log n) time.

Emphasizes O(log n) complexity and typical operations.

Source

RELATED TERMS

Prefix Sum Range Sum Query Frequency Table Range Update Sparse Table

COMPETING TERMS

Segment Tree Prefix Sum Array

KNOWLEDGE AREAS

Mathematics Software Engineering Data Science

TARGET AUDIENCE

Software Developer Data Engineer Data Scientist AI Engineer

EXTERNAL SOURCES

• Wikipedia - Fenwick tree
• CP-Algorithms - Clear explanation and code samples
• Topcoder - Intro and practice-focused guide

TOP QUESTIONS

What problems are best suited for a Fenwick Tree?

Fenwick Trees shine for dynamic prefix sums, frequency counts, inversion counting, and order statistics when combined with coordinate compression.

Category: Overview

How does a Fenwick Tree achieve O(log n) performance?

It stores partial sums based on least significant set bits, updating or querying only relevant aggregated ranges by traversing indices using bit operations.

Category: Concepts

How does a Fenwick Tree compare to a Segment Tree?

Fenwick Trees are simpler, smaller, and faster for prefix sums, while Segment Trees support broader range operations like min/max and flexible updates.

Category: Comparison

Can a Fenwick Tree support range updates?

Yes, by maintaining two BITs or using difference arrays, you can transform range updates into point updates while preserving O(log n) complexity.

Category: Design

What are common implementation pitfalls of Fenwick Trees?

Off-by-one errors from 1-based indexing and incorrect LSB operations are common. Carefully use i += i & -i and i -= i & -i patterns.

Category: Mistakes

Is a Fenwick Tree cache-friendly?

Yes, its array-based structure and sequential memory access patterns often lead to good cache performance compared to pointer-heavy trees.

Category: Performance

Can Fenwick Trees handle negative updates?

Absolutely. Updates can add or subtract values, and prefix sums naturally reflect cumulative totals, including negatives.

Category: Scope

How do I find the k-th order statistic using a Fenwick Tree?

Use a binary lifting technique over the BIT’s cumulative frequencies to locate the smallest index with a given cumulative sum.

Category: Technique

What is a real-world analogy for a Fenwick Tree?

Imagine receipts grouped by week, then month: to get a monthly total, you sum a few precomputed group totals instead of every receipt.

Category: Example