✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-211

Fenwick 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

Space complexity

O(n).

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

Array

  • 2

  • 4

  • 1

  • 3

  • 5

Query

Find the prefix sum from index 1 through index 4 using 1-based indexing.

Calculation

2 + 4 + 1 + 3 = 10

Result

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

Lowest Set Bit

i & -i

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

Language

Pseudocode

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

OperationComplexity

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

Space Complexity

O(n).

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.

Applications

  • Dynamic prefix sums

  • Range sum queries

  • Inversion counting

  • Frequency tables

  • Coordinate-compressed counting problems

  • Competitive programming

Related Topics

  • Segment Trees

  • Prefix Sums

  • Sparse Tables

  • Binary Representation

  • Range Query Algorithms

Practice Questions

QuestionAnswer

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.

  • Advanced Data Structures

Suggest a correction or source · More in Algorithms & Data Structures