Fenwick Tree-Based Online Range Sum

A Fenwick Tree is a compact array-based data structure used when you need to repeatedly query prefix sums and range sums while also modifying individual values. With a plain array, a point update is O(1) but a range sum is O(N); with a prefix sum array, a range sum is O(1) but updating a value in the middle requires recomputing all subsequent cumulative values, making it O(N). A Fenwick Tree offers a compromise, handling both operations in O(log N).

The original structure that Peter Fenwick proposed in 1994 was intended to efficiently maintain a dynamically changing cumulative frequency table. In the same paper, the author proposed the name binary indexed tree for this structure. It stores an implicit hierarchy of intervals within a single array. ([Fenwick 1994]¹)

The key insight is that each internal index i stores not a single value but the sum of an interval of length LSB(i) ending at i. Here, LSB(i) is the value represented by the lowest set bit in the binary representation, and it can be computed as i & -i for positive integers.

This structure is narrower in capability than a segment tree. If you try to pack general range minimum queries, lazy propagation, and arbitrary range updates into a single data structure, the simplicity of the Fenwick Tree disappears. Conversely, when the requirements align precisely with point updates and prefix/range sums, it is a compelling choice in terms of implementation size, memory usage, and cache footprint. Follow-up research also analyzes the practical utility of Fenwick-family structures alongside the interaction between index arithmetic and CPU cache. ([Marchini and Vigna 2020]², [arXiv preprint]³)

Text

External array: values[0..N)

Internal array: tree[1..N]

LSB(i) = i & -i

Range covered by tree[i]:
(i - LSB(i), i]
1-based indexing

Point Add:
Follow ancestor intervals from the index, adding delta

Prefix Sum:
Accumulate by following parent intervals from endExclusive

Range Sum:
sum([start, end)) = prefix(end) - prefix(start)

Complexity:
Point Add = O(log N)
Prefix Sum = O(log N)
Range Sum = O(log N)
Storage = O(N)

1. The Problem

Suppose a traffic analysis service divides a day into one-minute intervals and aggregates the number of requests per interval.

Text

Bucket count:
1,440

Input:
- Current incoming requests
- Late-arriving past requests
- Negative correction after deduplication

Query:
- Request count from 09:00 to 10:00
- Cumulative request count from midnight to now
- Request count in the last 15 minutes

Using a plain prefix sum array makes queries fast.

Text

prefix[minute]
Cumulative value from midnight up to (but not including) the current minute

09:00~10:00
= prefix[600] - prefix[540]

However, a problem arises when a request that occurred at 08:17 arrives late.

Text

values[497] += 1

All subsequent prefixes:
prefix[498..1440] += 1

A single update costs O(N).

On the other hand, maintaining only the original count array makes point updates O(1), but every range query must iterate over the corresponding range.

Using a Fenwick Tree handles both of the following operations in O(log N).

Text

add(497, +1)

rangeSum(540, 600)

The range convention for this common API is as follows.

Text

External index:
0-based

Range:
[startInclusive, endExclusive)

prefixSum(endExclusive):
Sum of [0, endExclusive)

Using a half-open range means the sum of an empty interval [x, x) naturally becomes 0, and it is easy to align with array slicing and loop boundaries.

2. Core Implementation

C++20

The C++ implementation uses std::int64_t for accumulated values. To prevent a situation where only some internal nodes are modified if an overflow occurs during an update, the implementation first collects all affected indices, validates every addition upfront, and only then applies them.

C++

#include <array>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <span>
#include <stdexcept>
#include <string>
#include <vector>

class FenwickTree final
{
public:
    explicit FenwickTree(std::size_t size)
        : size_(validatedSize(size)),
          tree_(size_ + 1, 0)
    {}

    FenwickTree(const FenwickTree&) = default;
    FenwickTree& operator=(const FenwickTree&) = default;

    FenwickTree(FenwickTree&&) noexcept = default;
    FenwickTree& operator=(FenwickTree&&) noexcept = default;

    void add(
        std::size_t index,
        std::int64_t delta)
    {
        validateIndex(index);

        std::array<
            std::size_t,
            std::numeric_limits<
                std::size_t>::digits> touched{};

        const std::size_t touchedCount =
            collectTouchedIndices(
                index,
                touched);

        validateUpdate(
            touched,
            touchedCount,
            delta);

        applyUpdate(
            touched,
            touchedCount,
            delta);
    }

    [[nodiscard]]
    std::int64_t prefixSum(
        std::size_t endExclusive) const
    {
        validateEnd(endExclusive, "endExclusive");

        std::int64_t result = 0;

        for (std::size_t index = endExclusive;
             index > 0;
             index -= leastSignificantBit(index))
        {
            result = checkedAdd(
                result,
                tree_[index]);
        }

        return result;
    }

    [[nodiscard]]
    std::int64_t rangeSum(
        std::size_t startInclusive,
        std::size_t endExclusive) const
    {
        validateRange(
            startInclusive,
            endExclusive);

        return checkedSubtract(
            prefixSum(endExclusive),
            prefixSum(startInclusive));
    }

    [[nodiscard]]
    std::int64_t getPointValue(
        std::size_t index) const
    {
        validateIndex(index);

        return rangeSum(
            index,
            index + 1);
    }

    [[nodiscard]]
    std::size_t getSize() const noexcept
    {
        return size_;
    }

private:
    static constexpr std::size_t maximumSize =
        10'000'000;

    std::size_t size_;
    std::vector<std::int64_t> tree_;

    [[nodiscard]]
    std::size_t collectTouchedIndices(
        std::size_t externalIndex,
        std::span<std::size_t> output) const
    {
        std::size_t count = 0;

        for (std::size_t index = externalIndex + 1;
             index <= size_;
             index += leastSignificantBit(index))
        {
            output[count] = index;
            count += 1;
        }

        return count;
    }

    void validateUpdate(
        std::span<const std::size_t> indices,
        std::size_t count,
        std::int64_t delta) const
    {
        for (std::size_t index = 0;
             index < count;
             index += 1)
        {
            ensureCanAdd(
                tree_[indices[index]],
                delta);
        }
    }

    void applyUpdate(
        std::span<const std::size_t> indices,
        std::size_t count,
        std::int64_t delta)
    {
        for (std::size_t index = 0;
             index < count;
             index += 1)
        {
            tree_[indices[index]] += delta;
        }
    }

    static std::size_t leastSignificantBit(
        std::size_t value) noexcept
    {
        return value & (~value + 1);
    }

    static void ensureCanAdd(
        std::int64_t left,
        std::int64_t right)
    {
        constexpr auto minimum =
            std::numeric_limits<std::int64_t>::min();

        constexpr auto maximum =
            std::numeric_limits<std::int64_t>::max();

        if (right > 0 && left > maximum - right)
        {
            throw std::overflow_error(
                "Fenwick Tree sum exceeds the int64 range.");
        }

        if (right < 0 && left < minimum - right)
        {
            throw std::overflow_error(
                "Fenwick Tree sum exceeds the int64 range.");
        }
    }

    static std::int64_t checkedAdd(
        std::int64_t left,
        std::int64_t right)
    {
        ensureCanAdd(left, right);
        return left + right;
    }

    static std::int64_t checkedSubtract(
        std::int64_t left,
        std::int64_t right)
    {
        constexpr auto minimum =
            std::numeric_limits<std::int64_t>::min();

        constexpr auto maximum =
            std::numeric_limits<std::int64_t>::max();

        if (right > 0 && left < minimum + right)
        {
            throw std::overflow_error(
                "Range sum exceeds the int64 range.");
        }

        if (right < 0 && left > maximum + right)
        {
            throw std::overflow_error(
                "Range sum exceeds the int64 range.");
        }

        return left - right;
    }

    void validateIndex(
        std::size_t index) const
    {
        if (index >= size_)
        {
            throw std::out_of_range(
                "index is out of bounds for the Fenwick Tree.");
        }
    }

    void validateEnd(
        std::size_t value,
        const char* name) const
    {
        if (value > size_)
        {
            throw std::out_of_range(
                std::string{name}
                + "is out of range.");
        }
    }

    void validateRange(
        std::size_t startInclusive,
        std::size_t endExclusive) const
    {
        validateEnd(startInclusive, "startInclusive");
        validateEnd(endExclusive, "endExclusive");

        if (startInclusive > endExclusive)
        {
            throw std::out_of_range(
                "The range is invalid.");
        }
    }

    [[nodiscard]]
    static std::size_t validatedSize(
        std::size_t size)
    {
        if (size == 0 || size > maximumSize)
        {
            throw std::invalid_argument(
                "size must be between 1 and 10,000,000 (inclusive).");
        }

        return size;
    }
};

Usage:

C++

FenwickTree counts{1'440};

counts.add(497, 1);
counts.add(540, 3);
counts.add(599, 2);

const std::int64_t morning =
    counts.rangeSum(540, 600);

The pre-update validation may look excessive in simple examples, but an implementation that checks for overflow while allowing partial mutation is worse, because the data structure silently becomes corrupted after a failure. (In practice, I notice that other implementers always include upfront validation, so I reflexively do the same.)

Python

Because Python's int has no fixed 64-bit overflow, the transactional overflow preflight used in C++ is unnecessary.

Python

from __future__ import annotations


class FenwickTree:
    _MAXIMUM_SIZE = 10_000_000

    def __init__(self, size: int) -> None:
        _validate_size(
            size,
            self._MAXIMUM_SIZE,
        )

        self._size = size
        self._tree = [0] * (size + 1)

    def add(
        self,
        index: int,
        delta: int,
    ) -> None:
        self._validate_index(index)
        _validate_integer(delta, "delta")

        internal_index = index + 1

        while internal_index <= self._size:
            self._tree[internal_index] += delta

            internal_index += (
                _least_significant_bit(
                    internal_index
                )
            )

    def prefix_sum(
        self,
        end_exclusive: int,
    ) -> int:
        self._validate_end(
            end_exclusive,
            "end_exclusive",
        )

        result = 0
        internal_index = end_exclusive

        while internal_index > 0:
            result += self._tree[internal_index]

            internal_index -= (
                _least_significant_bit(
                    internal_index
                )
            )

        return result

    def range_sum(
        self,
        start_inclusive: int,
        end_exclusive: int,
    ) -> int:
        self._validate_range(
            start_inclusive,
            end_exclusive,
        )

        return (
            self.prefix_sum(end_exclusive)
            - self.prefix_sum(start_inclusive)
        )

    def get_point_value(self, index: int) -> int:
        self._validate_index(index)

        return self.range_sum(
            index,
            index + 1,
        )

    def get_size(self) -> int:
        return self._size

    def _validate_index(self, index: int) -> None:
        _validate_integer(index, "index")

        if index < 0 or index >= self._size:
            raise IndexError(
                "index is out of range for the Fenwick Tree."
            )

    def _validate_end(
        self,
        value: int,
        field_name: str,
    ) -> None:
        _validate_integer(value, field_name)

        if value < 0 or value > self._size:
            raise IndexError(
                f"{field_name} is out of range."
            )

    def _validate_range(
        self,
        start_inclusive: int,
        end_exclusive: int,
    ) -> None:
        self._validate_end(
            start_inclusive,
            "start_inclusive",
        )
        self._validate_end(
            end_exclusive,
            "end_exclusive",
        )

        if start_inclusive > end_exclusive:
            raise ValueError(
                "start_inclusive는 "
                "Cannot be greater than end_exclusive."
            )


def _least_significant_bit(
    value: int,
) -> int:
    return value & -value


def _validate_size(
    size: int,
    maximum_size: int,
) -> None:
    _validate_integer(size, "size")

    if size < 1 or size > maximum_size:
        raise ValueError(
            "size must be at least 1 and"
            f"at most {maximum_size}."
        )


def _validate_integer(
    value: int,
    field_name: str,
) -> None:
    if (
        not isinstance(value, int)
        or isinstance(value, bool)
    ):
        raise TypeError(
            f"{field_name} must be an integer."
        )

Usage:

Python

counts = FenwickTree(1_440)

counts.add(497, 1)
counts.add(540, 3)
counts.add(599, 2)

morning = counts.range_sum(
    540,
    600,
)

In Python, a plain list stores object references, so its memory density is lower than a primitive array in C++ or C#. If the data size and query frequency are large enough, you can consider a native extension or an array-backed implementation, but first measure what fraction of total processing time this part actually accounts for.

C#

C# uses long[]. The code below uses relational patterns and therefore requires a C# 9 or later compiler. It collects the target nodes for an update via stackalloc and validates all internal sums before any overflow can occur.

using System;

public sealed class FenwickTree
{
    private const int MaximumSize = 10_000_000;
    private const int MaximumTreeDepth = 64;

    private readonly long[] tree;
    private readonly int size;

    public FenwickTree(int size)
    {
        ValidateSize(size);

        this.size = size;
        this.tree = new long[size + 1];
    }

    public void Add(
        int index,
        long delta)
    {
        this.ValidateIndex(index);

        Span<int> touched =
            stackalloc int[MaximumTreeDepth];

        int touchedCount =
            this.CollectTouchedIndices(
                index,
                touched);

        this.ValidateUpdate(
            touched,
            touchedCount,
            delta);

        this.ApplyUpdate(
            touched,
            touchedCount,
            delta);
    }

    public long PrefixSum(
        int endExclusive)
    {
        this.ValidateEnd(
            endExclusive,
            nameof(endExclusive));

        long result = 0;

        for (
            int index = endExclusive;
            index > 0;
            index -= LeastSignificantBit(index))
        {
            result = checked(
                result + this.tree[index]);
        }

        return result;
    }

    public long RangeSum(
        int startInclusive,
        int endExclusive)
    {
        this.ValidateRange(
            startInclusive,
            endExclusive);

        return checked(
            this.PrefixSum(endExclusive)
            - this.PrefixSum(startInclusive));
    }

    public long GetPointValue(int index)
    {
        this.ValidateIndex(index);

        return this.RangeSum(
            index,
            index + 1);
    }

    public int GetSize()
    {
        return this.size;
    }

    private int CollectTouchedIndices(
        int externalIndex,
        Span<int> output)
    {
        int count = 0;

        for (
            int index = externalIndex + 1;
            index <= this.size;
            index += LeastSignificantBit(index))
        {
            output[count] = index;
            count += 1;
        }

        return count;
    }

    private void ValidateUpdate(
        ReadOnlySpan<int> indices,
        int count,
        long delta)
    {
        for (int index = 0; index < count; index += 1)
        {
            _ = checked(
                this.tree[indices[index]]
                + delta);
        }
    }

    private void ApplyUpdate(
        ReadOnlySpan<int> indices,
        int count,
        long delta)
    {
        for (int index = 0; index < count; index += 1)
        {
            this.tree[indices[index]] += delta;
        }
    }

    private static int LeastSignificantBit(
        int value)
    {
        return value & -value;
    }

    private void ValidateIndex(int index)
    {
        if (index < 0 || index >= this.size)
        {
            throw new ArgumentOutOfRangeException(
                nameof(index));
        }
    }

    private void ValidateEnd(
        int value,
        string parameterName)
    {
        if (value < 0 || value > this.size)
        {
            throw new ArgumentOutOfRangeException(
                parameterName);
        }
    }

    private void ValidateRange(
        int startInclusive,
        int endExclusive)
    {
        this.ValidateEnd(
            startInclusive,
            nameof(startInclusive));
        this.ValidateEnd(
            endExclusive,
            nameof(endExclusive));

        if (startInclusive > endExclusive)
        {
            throw new ArgumentOutOfRangeException(
                nameof(startInclusive));
        }
    }

    private static void ValidateSize(int size)
    {
        if (size is < 1 or > MaximumSize)
        {
            throw new ArgumentOutOfRangeException(
                nameof(size));
        }
    }
}

Usage:

FenwickTree counts = new(1_440);

counts.Add(497, 1);
counts.Add(540, 3);
counts.Add(599, 2);

long morning =
    counts.RangeSum(540, 600);

If the checked update were applied directly inside the loop, an overflow on the third node would leave the first two nodes already modified. That is why the pre-validation and the actual application are kept separate.

TypeScript

TypeScript uses bigint for precise integer accumulation. JavaScript number has a limited safe integer range and therefore cannot be unconditionally relied upon for long-running cumulative counters.

TypeScript

export class FenwickTree
{
  static readonly #maximumSize =
    10_000_000;

  readonly #size: number;
  readonly #tree: bigint[];

  public static fromValues(
    values: readonly bigint[],
    signal?: AbortSignal,
  ): FenwickTree
  {
    if (values.length === 0) {
      throw new RangeError(
        "A Fenwick Tree cannot be created from an empty array.",
      );
    }

    const result =
      new FenwickTree(values.length);

    for (
      let internalIndex = 1;
      internalIndex <= values.length;
      internalIndex += 1
    ) {
      signal?.throwIfAborted();

      const value =
        values[internalIndex - 1];

      validateBigInt(value, "value");

      result.#tree[internalIndex] += value;

      const parentIndex =
        internalIndex
        + leastSignificantBit(
            internalIndex);

      if (parentIndex <= values.length) {
        result.#tree[parentIndex] +=
          result.#tree[internalIndex];
      }
    }

    return result;
  }

  public constructor(size: number)
  {
    validateSize(
      size,
      FenwickTree.#maximumSize,
    );

    this.#size = size;
    this.#tree =
      new Array<bigint>(size + 1)
        .fill(0n);
  }

  public add(
    index: number,
    delta: bigint,
  ): void
  {
    this.#validateIndex(index);
    validateBigInt(delta, "delta");

    let internalIndex = index + 1;

    while (internalIndex <= this.#size) {
      this.#tree[internalIndex] += delta;

      internalIndex +=
        leastSignificantBit(internalIndex);
    }
  }

  public prefixSum(
    endExclusive: number,
  ): bigint
  {
    this.#validateEnd(
      endExclusive,
      "endExclusive",
    );

    let result = 0n;
    let internalIndex = endExclusive;

    while (internalIndex > 0) {
      result += this.#tree[internalIndex];

      internalIndex -=
        leastSignificantBit(internalIndex);
    }

    return result;
  }

  public rangeSum(
    startInclusive: number,
    endExclusive: number,
  ): bigint
  {
    this.#validateRange(
      startInclusive,
      endExclusive,
    );

    return this.prefixSum(endExclusive)
      - this.prefixSum(startInclusive);
  }

  public getPointValue(
    index: number,
  ): bigint
  {
    this.#validateIndex(index);

    return this.rangeSum(
      index,
      index + 1,
    );
  }

  public getSize(): number
  {
    return this.#size;
  }

  #validateIndex(index: number): void
  {
    validateInteger(index, "index");

    if (index < 0 || index >= this.#size) {
      throw new RangeError(
        "The index is out of the Fenwick Tree's range.",
      );
    }
  }

  #validateEnd(
    value: number,
    fieldName: string,
  ): void
  {
    validateInteger(
      value,
      fieldName,
    );

    if (value < 0 || value > this.#size) {
      throw new RangeError(
        `${fieldName} is out of range.`,
      );
    }
  }

  #validateRange(
    startInclusive: number,
    endExclusive: number,
  ): void
  {
    this.#validateEnd(
      startInclusive,
      "startInclusive",
    );
    this.#validateEnd(
      endExclusive,
      "endExclusive",
    );

    if (startInclusive > endExclusive) {
      throw new RangeError(
        "startInclusive는 "
        + "Cannot be greater than endExclusive.",
      );
    }
  }
}

function leastSignificantBit(
  value: number,
): number
{
  return value & -value;
}

function validateSize(
  size: number,
  maximumSize: number,
): void
{
  validateInteger(size, "size");

  if (size < 1 || size > maximumSize) {
    throw new RangeError(
      "size must be at least 1"
      + `and at most ${maximumSize}.`,
    );
  }
}

function validateInteger(
  value: number,
  fieldName: string,
): void
{
  if (!Number.isSafeInteger(value)) {
    throw new TypeError(
      `${fieldName} must be a safe integer.`,
    );
  }
}

function validateBigInt(
  value: bigint,
  fieldName: string,
): void
{
  if (typeof value !== "bigint") {
    throw new TypeError(
      `${fieldName} must be a bigint.`,
    );
  }
}

Usage:

TypeScript

const counts =
  new FenwickTree(1_440);

counts.add(497, 1n);
counts.add(540, 3n);
counts.add(599, 2n);

const morning =
  counts.rangeSum(540, 600);

JavaScript bitwise operations go through ToInt32 and compute as signed 32-bit integers. The theoretical upper bound for a positive internal index under this scheme is 2^31 - 1. The reason this implementation caps the size at ten million is not the bitwise constraint but a separate policy to limit array allocation. If you need a larger index space, do not simply extend the bitwise operations as-is; instead, reconsider both the index representation and the memory policy together. This code block assumes noUncheckedIndexedAccess: false.

3. Call Site

The Fenwick Tree has no knowledge of time, dates, databases, or networks. An upper aggregation layer converts timestamps into minute indices, and a storage layer handles durability.

TypeScript

export type MinuteCountRepository = Readonly<{
  readDayAsync: (
    day: string,
    signal?: AbortSignal,
  ) => Promise<readonly bigint[]>;

  appendDeltaAsync: (
    day: string,
    minuteIndex: number,
    delta: bigint,
    signal?: AbortSignal,
  ) => Promise<void>;
}>;

const minuteCountPerDay = 1_440;

export class DailyTrafficIndex
{
  readonly #tree: FenwickTree;

  public constructor(
    tree = new FenwickTree(
      minuteCountPerDay,
    ),
  )
  {
    if (tree.getSize() !== minuteCountPerDay) {
      throw new RangeError(
        "The daily Fenwick Tree size is invalid.",
      );
    }

    this.#tree = tree;
  }

  public recordDelta(
    minuteIndex: number,
    delta: bigint,
  ): void
  {
    this.#tree.add(
      minuteIndex,
      delta,
    );
  }

  public countRange(
    startMinute: number,
    endMinute: number,
  ): bigint
  {
    return this.#tree.rangeSum(
      startMinute,
      endMinute,
    );
  }

  public countUntil(
    endMinute: number,
  ): bigint
  {
    return this.#tree.prefixSum(
      endMinute,
    );
  }
}

export async function rebuildDailyIndexAsync(
  repository: MinuteCountRepository,
  day: string,
  signal?: AbortSignal,
): Promise<DailyTrafficIndex>
{
  validateDay(day);

  const counts =
    await repository.readDayAsync(
      day,
      signal,
    );

  if (counts.length !== minuteCountPerDay) {
    throw new RangeError(
      "The daily count snapshot size is invalid.",
    );
  }

  signal?.throwIfAborted();

  return new DailyTrafficIndex(
    FenwickTree.fromValues(
      counts,
      signal,
    ),
  );
}

export async function recordDeltaDurablyAsync(
  repository: MinuteCountRepository,
  index: DailyTrafficIndex,
  day: string,
  minuteIndex: number,
  delta: bigint,
  signal?: AbortSignal,
): Promise<void>
{
  validateDay(day);

  await repository.appendDeltaAsync(
    day,
    minuteIndex,
    delta,
    signal,
  );

  index.recordDelta(
    minuteIndex,
    delta,
  );
}

function validateDay(day: string): void
{
  if (!/^\d{4}-\d{2}-\d{2}$/.test(day)) {
    throw new RangeError(
      "`day` must be in YYYY-MM-DD format.",
    );
  }
}

Separation of responsibilities:

Text

Timestamp Boundary
= Determine UTC or business timezone
= Convert timestamp → minute index

MinuteCountRepository
= Persistence for raw events and deltas
= Provides snapshots for restart recovery

DailyTrafficIndex
= Point deltas and range sums
= No external I/O

Query Service
= Convert user time range to minute range

Central Policy Handler
= Repository failures
= Cancellation
= Snapshot inconsistency handling

The Fenwick Tree is a process-local index, not a source of truth. Because the in-memory state is lost when the process terminates, you must rebuild it from an event log or a durable delta store.

4. Reading Order

Text

Is the external index 0-based?
→ Is the internal array 1-based?
→ Is index 0 never passed directly into the internal update loop?
→ What range does `tree[i]` cover?
→ Does update advance via `i += LSB(i)`?
→ Does query advance via `i -= LSB(i)`?
→ Is the prefix range `[0, end)`?
→ Is the range `[start, end)`?
→ Does an empty range return 0?
→ On overflow failure, is there no partial mutation left behind?
→ Is the policy for concurrent update/query explicitly documented?

Key invariants to keep in mind:

Text

tree[i]
=
values[
  i - LSB(i)
  ...
  i - 1
]

External 0-based,
internal 1-based

5. Boundaries and Misconceptions

The 1-based internal index is not cosmetic

The step size in a Fenwick Tree is LSB(i).

Text

i = 0

LSB(0)
= 0

If you start internal updates at 0, the next index is also 0, producing an infinite loop.

Text

0 += LSB(0)
0 += 0

Even if the external API is 0-based, you must convert to index + 1 internally.

A Fenwick Tree assumes a fixed index universe

It is well-suited for the following scenarios.

Text

- 1,440 minute buckets per day
- Product categories 0..N-1
- Compressed coordinates
- Fixed histogram buckets

It is harder to apply directly in the following cases.

Text

- Random UUID
- Inserting at a middle index
- Dynamically growing sort keys

If only the order of values matters and keys are large or sparse, use coordinate compression to create a dense index first, then apply the tree. If new keys are continuously inserted at runtime, an ordered tree or another data structure may be more appropriate.

It is a structure specialized for sum operations.

The core of the Fenwick Tree lies in prefix aggregation and inverse-like range computation.

Text

rangeSum(start, end)
=
prefix(end) - prefix(start)

To derive an arbitrary range query from two prefix values, associativity alone is insufficient; you also need an inverse operation that can undo the prefix portion. Addition satisfies this through subtraction, but min has no such inverse. A prefix-minimum variant restricted to monotonic updates does exist, but arbitrary point updates combined with arbitrary range minimum queries cannot be handled in the same way as this implementation. If you need that capability or complex lazy range updates, consider a structure such as a segment tree.

Handle predictable input failures with `Result` at public boundaries.

The data structure implementation in the previous section expresses out-of-range and invalid-size failures as language-level exceptions. However, if such failures are sufficiently predictable from inputs that callers can provide, a production API is better off returning an explicit Result<Success, Failure> instead of throwing. The call site can then branch on success and failure as structured values and log the failure code alongside the input.

That said, if prefixSum() and rangeSum() are called inside a loop that iterates tens of thousands of times, constructing and unwrapping a Result object on every call introduces additional costs: object allocation, reference tracking, success-flag branching, and value unwrapping, each of which varies by language and runtime. You cannot generalize whether these costs are always greater or smaller than an O(log N) traversal; you need a benchmark with fixed array size, runtime optimizations, value representations, and call distribution.

The solution is not to fall back to exceptions, but to separate the validation boundary from the computation boundary.

Text

External input
  ↓
validateRange
  ↓ Result<ValidatedRange, FenwickFailure>
Caller handles failure
  ↓
Validated range bundle
  ↓
rangeSumUnchecked
  ↓ bigint, long, int64_t
Repeated computation

unchecked does not mean validation is skipped; it is an internal contract stating that this function's inputs have already been validated. Keep this method inside the data structure and allow only a facade that has completed validation to call it. Do not expose it as a public API or pass unvalidated values into it.

The implementation in Section 2 does not include this path. If you introduce it, place it inside the class as a version of the existing rangeSum() with only the validation stripped out.

TypeScript

  // Inside `FenwickTree`. Only values that pass `ValidatedRange` are accepted.
  #rangeSumUnchecked(
    startInclusive: number,
    endExclusive: number,
  ): bigint
  {
    return this.prefixSum(endExclusive)
      - this.prefixSum(startInclusive);
  }

  public sumValidatedBatch(
    ranges: readonly ValidatedRange[],
  ): bigint[]
  {
    return ranges.map((range) =>
      this.#rangeSumUnchecked(
        range.startInclusive,
        range.endExclusive,
      ));
  }

Because prefixSum() also calls #validateEnd() internally, fully eliminating validation requires pushing the prefix traversal down an unchecked path as well. How far to strip it is a question the benchmark mentioned earlier should answer.

TypeScript

type Result<T, E> =
  | Readonly<{ ok: true; value: T }>
  | Readonly<{ ok: false; error: E }>;

type FenwickFailure =
  | Readonly<{ code: "invalid-size"; size: number }>
  | Readonly<{
      code: "invalid-range";
      startInclusive: number;
      endExclusive: number;
      size: number;
    }>;

type ValidatedRange = Readonly<{
  startInclusive: number;
  endExclusive: number;
}>;

const maximumSize = 10_000_000;

function validateRange(
  size: number,
  startInclusive: number,
  endExclusive: number,
): Result<ValidatedRange, FenwickFailure>
{
  if (
    !Number.isSafeInteger(size)
    || size < 1
    || size > maximumSize
  ) {
    return {
      ok: false,
      error: { code: "invalid-size", size },
    };
  }

  if (
    !Number.isSafeInteger(startInclusive)
    || !Number.isSafeInteger(endExclusive)
    || startInclusive < 0
    || startInclusive > endExclusive
    || endExclusive > size
  ) {
    return {
      ok: false,
      error: {
        code: "invalid-range",
        startInclusive,
        endExclusive,
        size,
      },
    };
  }

  return {
    ok: true,
    value: { startInclusive, endExclusive },
  };
}

The rejection criteria for invalid-size must match those of validateSize() in the Section 2 constructor. If only one side checks the upper bound, a size that passes boundary validation will be rejected by the constructor with an exception, and the failure you intended to represent as a Result leaks back out as an exception.

When each query comes in individually from outside, one Result per call is unavoidable. If you pre-validate the query requests into a ValidatedRange[] and compute the raw sums in a single batch, the failure representation stays at the input boundary and the loop only performs value and array accesses. In C++23 you can use std::expected; in C++20, a project-owned equivalent result type. In C# you can apply a project-owned Result<T, E>, and in TypeScript a discriminated union, following the same principle.

Compare before and after introducing Result using the same query sequence.

Implementation	Validation and return strategy	Measurement purpose
Raw internal computation	Validated range, raw sum returned	Baseline of the data structure itself
Result per call	Each query performs Result construction and unwrapping	Cost of the simplest safe API
Boundary Result with batch computation	Validate once during batch setup, raw sum inside	Cost of separating safety from the hot path

Implementation: Raw internal computation
Validation and return strategy: Validated range, raw sum returned
Measurement purpose: Baseline of the data structure itself

Implementation: Result per call
Validation and return strategy: Each query performs Result construction and unwrapping
Measurement purpose: Cost of the simplest safe API

Implementation: Boundary Result with batch computation
Validation and return strategy: Validate once during batch setup, raw sum inside
Measurement purpose: Cost of separating safety from the hot path

Use the same N, update-to-query ratio, range length distribution, random seed, and integer width across all benchmarks. Look at not only total time but also allocation count, GC or allocator activity, branch misses, cache misses, and per-query latency. Before results are in, avoid declaring either "Result is slow" or "Result overhead is negligible." (Premature optimization is not some special concept; optimization without measurement is what makes it premature.)

Exceptions to this principle are not for expressing predictable validation failures. Out-of-range indices, incorrect sizes, and format errors should be returned as Failure values. Failures for which no recovery path has been separately designed, such as out-of-memory, corrupted internal state, or an internal caller that violates a contract, should be left to the language's and system's fatal boundary policy.

Negative deltas are permitted, but their semantics should be verified

This implementation supports negative corrections.

Text

Duplicate event cancellation:
add(minute, -1)

You can confirm that the range sum itself has no issues.

However, the order-statistic extension that uses a cumulative count to find "the first index where the prefix sum reaches or exceeds X" requires the prefix sum to be monotonically increasing. If negative values are present, that search condition can break.

A prefix array is often the better choice

Text

Data:
Created once initially

Update:
None

Query:
Millions of times

In such cases, the cumulative sum array provides the following performance characteristics.

Text

Build:
O(N)

Range Query:
O(1)

The O(log N) query of a Fenwick Tree is unnecessary overhead when queries are rare; conversely, if there are almost no queries and only frequent updates, maintaining a plain array may be simpler.

A Fenwick Tree is justified when both updates and queries occur repeatedly.

A linear array does not mean all accesses are contiguous

The storage is a dense array, but the indices visited during updates and queries advance in powers-of-two intervals.

Text

update 5:
6 → 8 → 16 → 32 ...

query 27:
27 → 26 → 24 → 16 ...

With large data structures, this index pattern and the cache hierarchy both affect performance. The compactness of the Fenwick structure is an advantage, but on real CPUs a benchmark that includes array size and query distribution is necessary. Related research also finds that the interaction between Fenwick index arithmetic and cache structure is significant for practical performance. ([Marchini and Vigna 2020]⁴)

Concurrent access is not automatically safe

An update modifies multiple tree nodes in sequence.

Text

Update `tree[6]`
Update `tree[8]`
Update `tree[16]`

If a query runs concurrently, it may observe a mixture of pre-update and post-update values.

Possible policies:

Text

- Single owner actor
- read/write lock
- Replace immutable snapshot after update batch
- Independent tree per shard
- Atomic node update with acceptable weak consistency

Making each node atomic alone does not make the entire query snapshot atomic.

The overflow policy is part of the data structure

In C++ and C#, internal nodes store the sum of multiple elements, so the accumulated sum can exceed 64 bits even when individual elements are small.

Bad implementation:

Text

node 1 update succeeded
node 2 update succeeded
overflow exception at node 3

Result:
only some nodes updated
→ internal invariant corrupted

Therefore, you can say that one of the following is required.

Text

- Pre-validate all nodes for overflow before updating
- Wider integer type
- Saturation policy
- Domain with explicit modulo arithmetic

Python uses arbitrary-precision integers, so there is no overflow, but the cost of large integer arithmetic grows with the magnitude of the values.

Data persistence and the data structure are separate concerns

The Fenwick Tree is a query index.

Text

Source of truth:
event log, DB, durable snapshot

Derived index:
Fenwick Tree

If you apply an update to the in-memory tree first and then the database write fails, the two states diverge. You should either commit the persistent delta first and then update the memory index, or define a clear ordering that allows a rebuild on failure. The recordDeltaDurablyAsync() in Section 3 encodes this ordering in code: if appendDeltaAsync() fails, the exception propagates as-is and the memory index is left untouched.

Scenarios that fail in production:

Text

Starting the internal index from 0 causes an infinite loop
Mixing inclusive and exclusive ranges
Silently clamping an `end` value larger than `size`
Negative indices behave differently across languages
Only some tree nodes are updated after an overflow
Implementing a min query via prefix subtraction
Multiple threads updating without synchronization
Using a process-local tree as the source of truth
Allocating a huge array for sparse 64-bit keys
Using a Fenwick Tree even for data with no updates

6. Incorrect Examples

The following implementation uses the external 0-based index as-is internally.

TypeScript

class FenwickTreeBad
{
  readonly #tree: number[];

  public constructor(size: number)
  {
    this.#tree =
      new Array<number>(size).fill(0);
  }

  public add(
    index: number,
    delta: number,
  ): void
  {
    while (index < this.#tree.length) {
      this.#tree[index] += delta;
      index += index & -index;
    }
  }
}

Behavior of add(0, 1):

Text

index = 0

index & -index
= 0

다음 index
= 0 + 0
= 0

It becomes an infinite loop.

Other issues:

Text

- There is no input validation.
- `NaN` and `Infinity` are allowed.
- The cumulative sum can exceed `Number.MAX_SAFE_INTEGER`.
- The internal array length and valid index rules are unclear.
- The inclusive/exclusive semantics of the range are undefined.

Correct structure:

Text

externalIndex = 0

internalIndex
= externalIndex + 1
= 1

LSB(1)
= 1

Next:
1 → 2 → 4 → 8

7. Production Extensions

O(N) initial construction

If an initial snapshot already exists, O(N) build is possible instead of O(N log N) construction that calls add() on each element. FenwickTree.fromValues() in Section 2 is a static constructor defined inside the class, and rebuildDailyIndexAsync() in Section 3 uses this path. It accepts an optional AbortSignal to check for cancellation even during the construction of a large snapshot.

Each node's current partial sum is forwarded directly to its parent node.

Text

Reflect `values[i-1]` into `tree[i]`
→ parent = i + LSB(i)
→ tree[parent] += tree[i]

The difference is small with an initial 1,440-minute snapshot, but becomes significant when rebuilding millions of buckets or regenerating the index frequently.

Reference array-based state testing

TypeScript

import assert from "node:assert/strict";
import test from "node:test";

import { FenwickTree } from "./fenwick-tree.js";

test("A Fenwick Tree is equivalent to the range sum of the underlying array", () =>
{
  const size = 512;
  const tree = new FenwickTree(size);
  const reference =
    new Array<bigint>(size).fill(0n);

  const random =
    createDeterministicRandom(0x5eed);

  for (
    let step = 0;
    step < 50_000;
    step += 1
  ) {
    const operation =
      random() % 2;

    if (operation === 0) {
      const index =
        random() % size;

      const delta =
        BigInt(
          (random() % 201) - 100);

      tree.add(index, delta);
      reference[index] += delta;

      continue;
    }

    const first =
      random() % (size + 1);

    const second =
      random() % (size + 1);

    const start = Math.min(
      first,
      second,
    );

    const end = Math.max(
      first,
      second,
    );

    assert.equal(
      tree.rangeSum(start, end),
      sumReference(
        reference,
        start,
        end),
    );
  }
});

test("The sum of an empty range is 0", () =>
{
  const tree = new FenwickTree(10);

  tree.add(5, 100n);

  assert.equal(
    tree.rangeSum(5, 5),
    0n,
  );
});

test("Handle the first index and the last index", () =>
{
  const tree = new FenwickTree(10);

  tree.add(0, 3n);
  tree.add(9, 7n);

  assert.equal(
    tree.rangeSum(0, 1),
    3n,
  );

  assert.equal(
    tree.rangeSum(9, 10),
    7n,
  );

  assert.equal(
    tree.rangeSum(0, 10),
    10n,
  );
});

function sumReference(
  values: readonly bigint[],
  start: number,
  end: number,
): bigint
{
  let result = 0n;

  for (
    let index = start;
    index < end;
    index += 1
  ) {
    result += values[index];
  }

  return result;
}

function createDeterministicRandom(
  seed: number,
): () => number
{
  let state = seed >>> 0;

  return () =>
  {
    state = (
      Math.imul(state, 1_664_525)
      + 1_013_904_223
    ) >>> 0;

    return state >>> 16;
  };
}

The lower bits of an LCG have short periods, so this test restricts the return value to state >>> 16 and ensures that random() % 2 or random() % 512 does not depend directly on the lower bits. Since this harness has a size of 512, a 16-bit return value is sufficient. For a harness with size 65,536 or larger, you should retain the raw state and then derive the range from the upper portion, for example as Math.floor((state / 0x1_0000_0000) * upperBound).

Execution verification scope

Each language implementation is validated against a reference array using the same deterministic query sequence: seed 0x5eed, size 512, 50,000 interleaved point add and range sum operations, with every query result compared against the direct sum from the reference array. This verification also covers the following failure paths.

Text

- size 0, exceeding the maximum size
- negative index, point index equal to size
- startInclusive > endExclusive, endExclusive > size
- empty range, first index, last index, full range
- C++ and C# overflow pre-validation, and whether the internal array remains unchanged
- TypeScript `fromValues` rejection of an empty array and the O(N) build result
- `rebuild` with a valid snapshot and a snapshot of incorrect length

TypeScript is compiled in strict mode with noUncheckedIndexedAccess: false, C# as a Release build targeting C# 9 or later, and C++ with -std=c++20 -Wall -Wextra -Werror -pedantic. For Python, syntax is first checked with python3 -m py_compile <file path>, followed by the same reference array validation.

Core test invariants:

Text

prefixSum(0) = 0

rangeSum(i, i) = 0

rangeSum(i, i+1)
= getPointValue(i)

rangeSum(0, N)
Sum of all points

After `add(i, d)`:
Only ranges containing `i` change by `d`

Benchmark comparison

The following three structures should be benchmarked together.

Text

Raw Array:
Update O(1)
Query O(range length)

Prefix Array:
Update O(N)
Query O(1)

Fenwick Tree:
Update O(log N)
Query O(log N)

Benchmark variables:

Text

- N
Update:Query ratio
Query range length distribution
Random/clustered index distribution
Thread count
- Integer width
Initial build frequency

The fact that a Fenwick Tree is an algorithmically balanced choice is a separate claim from asserting that it is the fastest option under the current workload.

Operational metrics

Text

fenwick.update.count
fenwick.query.count
fenwick.update.duration_ns
fenwick.query.duration_ns
fenwick.rebuild.count
fenwick.rebuild.duration_ms
fenwick.size
fenwick.overflow.count

Do not use bucket indices or user IDs as metric labels.

8. C++ / Python / C# / TypeScript Comparison Notes

Language	Internal Value	Storage Representation	Key Risks
C++	`int64_t`	`vector<int64_t>`	Partial mutation after overflow
Python	arbitrary `int`	`list[int]`	Object memory and interpreter overhead
C#	`long`	`long[]`	The illusion of atomicity with checked updates
TypeScript	`bigint`	`bigint[]`	Performance and JSON serialization constraints

Language: C++
Internal Value: int64_t
Storage Representation: vector<int64_t>
Key Risks: Partial mutation after overflow

Language: Python
Internal Value: arbitrary int
Storage Representation: list[int]
Key Risks: Object memory and interpreter overhead

Language: C#
Internal Value: long
Storage Representation: long[]
Key Risks: The illusion of atomicity with checked updates

Language: TypeScript
Internal Value: bigint
Storage Representation: bigint[]
Key Risks: Performance and JSON serialization constraints

C++

std::vector<int64_t> is contiguous and has clear ownership semantics. Using std::array for a touched-index preflight check performs transactional overflow validation without heap allocation per update.

If the required value range is clearly small, you can remove the overflow check, but this must be proven through domain invariants rather than benchmarks.

Python

Python integers are immune to overflow, but each tree element may be represented as a separate Python object reference, resulting in low memory density.

This is sufficient when N is small or the number of queries within a Python orchestration layer is limited. If you need to process millions of nodes at high frequency, consider a native implementation.

C#

long[] is compact, and you can use stackalloc to manage temporary indices along the update path.

checked only detects arithmetic overflow; it does not turn multiple array modifications into a transaction. This is why pre-validation is necessary.

TypeScript

bigint is precise but comes with the following trade-offs.

Text

- Arithmetic cost may exceed that of `number`
- `JSON.stringify` cannot handle `bigint` directly
- Cannot mix arithmetic operations with `number`

If there is an invariant that the maximum accumulated sum of values stays within Number.MAX_SAFE_INTEGER, a number-based implementation can be faster. In that case, you must either apply safe-integer checks to all update and query results, or enforce the upper bound through input validation policy.

JavaScript's bitwise ToInt32 conversion places a theoretical upper bound of 2^31 - 1 on positive internal indices. The effective upper bound of this implementation is 10,000,000, which is smaller, and serves as a memory policy that limits array allocation.

Common Contract

Even though the integer types differ across the four languages, the index semantics must remain the same.

Text

Public:
0-based

Prefix:
[0, endExclusive)

Range:
[startInclusive, endExclusive)

Internal:
1-based

LSB:
Computed for positive indices only

9. Further Considerations

At what update-to-query ratio does a Fenwick Tree actually outperform a prefix sum array in practice?
When negative deltas are permitted, should the cumulative rank search feature be explicitly prohibited?
When multiple threads issue queries concurrently, which consistency model is required: locking, copy-on-write snapshots, or shard-local trees?
In domains where 64-bit overflow is possible, which policy is appropriate: wider integers, saturation arithmetic, or fail-fast behavior?
When sparse timestamps are coordinate-compressed, how should the cost of rebuilding indices when a new timestamp arrives be handled?
Is the complexity of building an initial snapshot in O(N) justified given the actual frequency of rebuilds?

10. Summary

The Fenwick Tree performs both point updates and prefix/range sum queries in O(log N) time.
The external index should be 0-based, but internally it must be converted to 1-based.
tree[i] stores the range sum over an interval of length LSB(i).
The range API is fixed to [start, end) to reduce off-by-one errors.
In C++ and C#, pre-validation is necessary to ensure no partial mutation remains after an overflow failure.
If there are no updates, a prefix array may be more appropriate; for general compound range operations, a segment tree may be a better fit.

Text

Don't recompute the entire prefix sum just because a single value changed.

Update only the binary intervals each index is responsible for,
and compute any desired range sum as the difference of two prefix sums.

Footnotes

"A New Data Structure for Cumulative Frequency Tables" ↩
"Compact Fenwick Trees for Dynamic Ranking and Selection" ↩
"Compact Fenwick Trees for Dynamic Ranking and Selection (arXiv preprint)" ↩
https://doi.org/10.1002/spe.2791 "Compact Fenwick Trees for Dynamic Ranking and Selection" ↩

1. The Problem

2. Core Implementation

C++20

Python

C#

TypeScript

3. Call Site

4. Reading Order

5. Boundaries and Misconceptions

The 1-based internal index is not cosmetic

A Fenwick Tree assumes a fixed index universe

It is a structure specialized for sum operations.

Handle predictable input failures with Result at public boundaries.

Negative deltas are permitted, but their semantics should be verified

A prefix array is often the better choice

A linear array does not mean all accesses are contiguous

Concurrent access is not automatically safe

The overflow policy is part of the data structure

Data persistence and the data structure are separate concerns

6. Incorrect Examples

7. Production Extensions

O(N) initial construction

Reference array-based state testing

Execution verification scope

Benchmark comparison

Operational metrics

8. C++ / Python / C# / TypeScript Comparison Notes

C++

Python

C#

TypeScript

Common Contract

9. Further Considerations

10. Summary

Footnotes

Handle predictable input failures with `Result` at public boundaries.