Fenwick Tree-Based Online Range Sum

A Fenwick Tree is a dense array-backed structure for the case where you keep modifying one value while repeatedly querying prefix sums and range sums. A plain array gives O(1) point updates but O(N) range sums; a cumulative array is the other way around, O(1) range sums but O(N) as soon as you change a middle value, because every later cumulative entry has to be recomputed. A Fenwick Tree trades both of those for 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

A plain cumulative array makes the reads themselves fast.

Text

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

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

The trouble starts when a request from 08:17 arrives late.

Text

values[497] += 1

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

One update costs O(N), which hurts.

The other way round, keeping only the raw count array makes point updates O(1), but every range query has to walk the whole range.

A Fenwick Tree brings both operations down to O(log N).

Text

add(497, +1)

rangeSum(540, 600)

The shared API fixes the range convention like this.

Text

External index:
0-based

Range:
[startInclusive, endExclusive)

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

With a half-open range, an empty interval [x, x) sums to 0 for free, and the bounds line up 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);

Pre-validating the update looks like overkill in a toy example, but checking for overflow while letting a partial mutation through is the worse choice — after a failure the structure is quietly broken. (Every other implementation I read has the pre-check in it, so I put it in by reflex too.)

Python

Python's int has no fixed 64-bit overflow, so the transactional overflow preflight that C++ needs does not apply here.

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,
)

A plain Python list holds object references, so it gets less data per byte than a primitive array in C++ or C#. Once the data size and query rate are big enough, a native extension or an array-backed implementation is worth considering — but measure how much of total processing time this part actually takes first.

C#

C# uses long[], and the code below relies on relational patterns, so it needs a C# 9 or later compiler. It gathers the nodes an update will touch with stackalloc and validates every internal sum before overflow can happen.

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);

Applying the checked update straight inside the loop would leave the first two nodes already changed when overflow hits the third, so pre-validation and application are pulled apart.

TypeScript

TypeScript uses bigint when the integer accumulation has to be exact. A JavaScript number has only a narrow safe-integer range, so it is not automatically correct for counters that accumulate over a long time.

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 run as signed 32-bit integers, so a positive internal index has a theoretical ceiling of 2^31 - 1. The reason this implementation caps size at ten million is not that bitwise constraint but a separate policy to bound array allocation. If you need more index space, do not just loosen the bitwise arithmetic; decide the index representation and the memory policy together. This code block assumes noUncheckedIndexedAccess: false.

3. Call Site

The Fenwick Tree knows nothing about time, dates, the DB, or the network. Turning a timestamp into a minute index is the aggregation layer's job, and durability belongs to the storage layer.

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. When the process goes down the memory state goes with it, so it has to be rebuilt 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

What sets the step in a Fenwick Tree is LSB(i).

Text

i = 0

LSB(0)
= 0

Starting the internal update at 0 gives the next index 0 as well, which loops forever.

Text

0 += LSB(0)
0 += 0

Even if the public API stays 0-based, the index has to become index + 1 on the way in.

A Fenwick Tree assumes a fixed index universe

It fits this kind of example well.

Text

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

These cases are hard to apply as-is.

Text

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

If only the ordering matters and the keys are large or sparse, compress the coordinates into a dense index first and then use the tree. If new keys keep arriving at runtime, an ordered tree or some other structure is a better fit.

It is a structure specialized for sum operations.

The center of the Fenwick Tree is the prefix aggregate plus an inverse-like range computation.

Text

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

Turning an arbitrary range query into two prefixes takes more than associativity: you need an inverse that can undo the leading part. Subtraction plays that role for sums, but min has no such inverse. A prefix-minimum variant exists as long as the updates stay monotonic. That still does not let you handle arbitrary point updates plus arbitrary range minima the way this implementation does. If you need either that or complex lazy range updates, look at something like a segment tree.

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

The implementations in the previous section throw language-level exceptions for out-of-range indices and bad sizes. Where a failure is fully predictable from input a caller can supply, though, a product API is better off returning an explicit Result<Success, Failure> instead of throwing: the caller splits success and failure as structured values and can record the failure code together with the input.

But once prefixSum() and rangeSum() run in a loop of tens of thousands of iterations, building and unwrapping a Result on every call adds cost: object allocation, reference tracking, branching on the success flag, value unwrapping — how much depends on the language and runtime. You cannot generalize that it is always larger or always smaller than the O(log N) descent. What you need is a benchmark with array size, runtime optimizations, value representation and call distribution held fixed.

The fix is not to go back to exceptions; it is to split 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 that this method's input has already been validated. So keep the method inside the data structure and let only a facade that has finished validating call it. Do not expose it as a public API, and do not pass it unvalidated values.

The Section 2 implementation has no such path. To add one, put it inside the class as the existing rangeSum() with 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,
      ));
  }

prefixSum() calls #validateEnd() again internally, so removing validation entirely means pushing the prefix descent onto the unchecked path too. How far to go is decided by the benchmark mentioned earlier.

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 },
  };
}

invalid-size has to use the same rule as validateSize() in the Section 2 constructor. If only one side checks the upper bound, a size that passed boundary validation is rejected by the constructor with an exception, and the failure you meant to express 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 the version before and after Result with 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

Hold N, the update:query ratio, the range-length distribution, the random seed and the integer width identical. Do not watch total time alone; watch allocation count, GC or allocator activity, branch misses, cache misses and per-query latency as well. Until the results are in, do not declare either "Result is slow" or "Result cost is negligible." (Premature optimization is nothing special — optimization without measurement is what makes it premature.)

The exception in this principle is not a way to express predictable validation failures. Out-of-range indices, bad sizes and format errors come back as Failure values. Failures with no designed recovery path — out of memory, corrupted internal state, an internal caller that breaks the contract — are left to the language's and the system's fatal boundary policy.

Negative deltas are permitted, but their semantics should be verified

This implementation accepts negative corrections too.

Text

Duplicate event cancellation:
add(minute, -1)

The range sums themselves check out fine.

Using a cumulative count for the order-statistic extension that finds "the first index whose prefix sum is at least X" requires the prefix sum to be monotonic. Once negatives are in the mix, that search condition breaks.

A prefix array is often the better choice

Text

Data:
Created once initially

Update:
None

Query:
Millions of times

In this case the cumulative array gives the performance below.

Text

Build:
O(N)

Range Query:
O(1)

The O(log N) query of a Fenwick Tree is just unnecessary cost. Conversely, with almost no queries and a lot of updates, holding just the raw array is simpler.

In the end a Fenwick Tree only earns its keep when updates and queries both repeat.

A linear array does not mean all accesses are contiguous

The storage is a dense array, but the indices an update or query visits jump in powers-of-two steps.

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 changes several tree nodes one after another.

Text

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

If a query lands in between, it sees a sum that mixes values from before and after the update.

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 does not make the whole query snapshot atomic.

The overflow policy is part of the data structure

In C++ and C#, an internal node holds the sum of several elements, so the accumulated total can pass 64 bits even when each element is 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

So you have to pick one of the following.

Text

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

Python has arbitrary-precision integers, so there is no overflow, but large-integer arithmetic gets more expensive as the values grow.

Data persistence and the data structure are separate concerns

The Fenwick Tree is only a query index.

Text

Source of truth:
event log, DB, durable snapshot

Derived index:
Fenwick Tree

Apply the update to the in-memory tree first and a failed DB write splits the two states. Either commit the durable delta first and then update the memory index, or pin down an ordering that can rebuild on failure. Section 3's recordDeltaDurablyAsync() is that ordering baked into code: when appendDeltaAsync() fails, the exception goes straight up 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

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

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 loops forever.

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

With an initial snapshot already in hand you can do an O(N) build instead of the O(N log N) construction that calls add() per element. FenwickTree.fromValues() in Section 2 is a static constructor defined inside the class, and rebuildDailyIndexAsync() in Section 3 takes that path. It accepts an optional AbortSignal, so cancellation is checked even while a large snapshot is being built.

Each node hands its current partial sum straight 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

Every language implementation is checked against a reference array with the same deterministic query sequence: seed 0x5eed, size 512, 50,000 mixed point adds and range sums, with each query result compared to the direct sum over the reference array. The verification also covers the failure paths below.

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

These three structures have to be compared side by side.

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

A Fenwick Tree being an algorithmically balanced choice is a different claim from it being the fastest thing on 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

Bucket indices and user IDs do not belong in 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 the ownership is clear. A touched-index preflight with std::array gives transactional overflow checking without a heap allocation per update.

If the value range is known to be small, the overflow check can go, but that is something a domain invariant has to establish, not a benchmark.

Python

Python integers never overflow, but each tree element may end up as a separate Python object reference, which keeps memory density low.

That is enough when N is small or the query count inside a Python orchestration stays limited. For millions of nodes at a high rate, look at a native implementation.

C#

long[] is compact, and stackalloc can hold the temporary indices along the update path.

checked catches arithmetic overflow but does not bind several array writes into a transaction — that is why the pre-validation is there.

TypeScript

bigint is exact, but it comes with these trade-offs.

Text

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

Given an invariant that the largest accumulated sum stays inside Number.MAX_SAFE_INTEGER, a number implementation can be faster. In that case every update and query result needs a safe-integer check, or the ceiling has to be guaranteed by input policy.

The ToInt32 conversion of JavaScript bitwise operations puts a theoretical ceiling of 2^31 - 1 on a positive internal index. The effective ceiling here is 10,000,000, which is lower, and that is a memory policy to bound array allocation.

Common Contract

The four languages use different integer types, but the index meaning has to be identical.

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 beat a cumulative array?
If negative deltas are allowed, shouldn't the cumulative rank search be banned outright?
When several threads query, which consistency model do we need: a lock, a copy-on-write snapshot, or a shard-local tree?
In a domain where 64-bit overflow is possible, which policy fits: wider integers, saturation, or fail-fast?
With sparse timestamps coordinate-compressed, how should the index rebuild cost be handled when a new timestamp arrives?
Does the complexity of building the initial snapshot in O(N) pay off at the actual rebuild frequency?

10. Summary

A Fenwick Tree does point updates and prefix/range sums all in O(log N).
Keep the external index 0-based and convert to 1-based on the inside, always.
tree[i] holds the range sum of an interval of length LSB(i).
The range API is pinned to [start, end), which cuts down off-by-one errors.
In C++ and C#, pre-validation keeps a failed overflow from leaving a partial mutation behind.
With no updates a prefix array may fit better; with many compound range operations a segment tree may.

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" ↩

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

A plain cumulative array makes the reads themselves fast.

Text

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

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

The trouble starts when a request from 08:17 arrives late.

Text

values[497] += 1

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

One update costs O(N), which hurts.

The other way round, keeping only the raw count array makes point updates O(1), but every range query has to walk the whole range.

A Fenwick Tree brings both operations down to O(log N).

Text

add(497, +1)

rangeSum(540, 600)

The shared API fixes the range convention like this.

Text

External index:
0-based

Range:
[startInclusive, endExclusive)

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

With a half-open range, an empty interval [x, x) sums to 0 for free, and the bounds line up with array slicing and loop boundaries.

2. Core Implementation

C++20

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);

Python

Python's int has no fixed 64-bit overflow, so the transactional overflow preflight that C++ needs does not apply here.

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,
)

C#

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);

Applying the checked update straight inside the loop would leave the first two nodes already changed when overflow hits the third, so pre-validation and application are pulled apart.

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);

3. Call Site

The Fenwick Tree knows nothing about time, dates, the DB, or the network. Turning a timestamp into a minute index is the aggregation layer's job, and durability belongs to the storage layer.

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. When the process goes down the memory state goes with it, so it has to be rebuilt 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

What sets the step in a Fenwick Tree is LSB(i).

Text

i = 0

LSB(0)
= 0

Starting the internal update at 0 gives the next index 0 as well, which loops forever.

Text

0 += LSB(0)
0 += 0

Even if the public API stays 0-based, the index has to become index + 1 on the way in.

A Fenwick Tree assumes a fixed index universe

It fits this kind of example well.

Text

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

These cases are hard to apply as-is.

Text

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

It is a structure specialized for sum operations.

The center of the Fenwick Tree is the prefix aggregate plus an inverse-like range computation.

Text

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

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

The fix is not to go back to exceptions; it is to split 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

The Section 2 implementation has no such path. To add one, put it inside the class as the existing rangeSum() with 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,
      ));
  }

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 },
  };
}

Compare the version before and after Result with 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

Negative deltas are permitted, but their semantics should be verified

This implementation accepts negative corrections too.

Text

Duplicate event cancellation:
add(minute, -1)

The range sums themselves check out fine.

A prefix array is often the better choice

Text

Data:
Created once initially

Update:
None

Query:
Millions of times

In this case the cumulative array gives the performance below.

Text

Build:
O(N)

Range Query:
O(1)

The O(log N) query of a Fenwick Tree is just unnecessary cost. Conversely, with almost no queries and a lot of updates, holding just the raw array is simpler.

In the end a Fenwick Tree only earns its keep when updates and queries both repeat.

A linear array does not mean all accesses are contiguous

The storage is a dense array, but the indices an update or query visits jump in powers-of-two steps.

Text

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

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

Concurrent access is not automatically safe

An update changes several tree nodes one after another.

Text

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

If a query lands in between, it sees a sum that mixes values from before and after the update.

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 does not make the whole query snapshot atomic.

The overflow policy is part of the data structure

In C++ and C#, an internal node holds the sum of several elements, so the accumulated total can pass 64 bits even when each element is 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

So you have to pick one of the following.

Text

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

Python has arbitrary-precision integers, so there is no overflow, but large-integer arithmetic gets more expensive as the values grow.

Data persistence and the data structure are separate concerns

The Fenwick Tree is only a query index.

Text

Source of truth:
event log, DB, durable snapshot

Derived index:
Fenwick Tree

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

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

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 loops forever.

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

Each node hands its current partial sum straight 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;
  };
}

Execution verification scope

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

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

These three structures have to be compared side by side.

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

A Fenwick Tree being an algorithmically balanced choice is a different claim from it being the fastest thing on 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

Bucket indices and user IDs do not belong in 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 the ownership is clear. A touched-index preflight with std::array gives transactional overflow checking without a heap allocation per update.

If the value range is known to be small, the overflow check can go, but that is something a domain invariant has to establish, not a benchmark.

Python

Python integers never overflow, but each tree element may end up as a separate Python object reference, which keeps memory density low.

That is enough when N is small or the query count inside a Python orchestration stays limited. For millions of nodes at a high rate, look at a native implementation.

C#

long[] is compact, and stackalloc can hold the temporary indices along the update path.

checked catches arithmetic overflow but does not bind several array writes into a transaction — that is why the pre-validation is there.

TypeScript

bigint is exact, but it comes with these trade-offs.

Text

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

Common Contract

The four languages use different integer types, but the index meaning has to be identical.

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 beat a cumulative array?
If negative deltas are allowed, shouldn't the cumulative rank search be banned outright?
When several threads query, which consistency model do we need: a lock, a copy-on-write snapshot, or a shard-local tree?
In a domain where 64-bit overflow is possible, which policy fits: wider integers, saturation, or fail-fast?
With sparse timestamps coordinate-compressed, how should the index rebuild cost be handled when a new timestamp arrives?
Does the complexity of building the initial snapshot in O(N) pay off at the actual rebuild frequency?

10. Summary

A Fenwick Tree does point updates and prefix/range sums all in O(log N).
Keep the external index 0-based and convert to 1-based on the inside, always.
tree[i] holds the range sum of an interval of length LSB(i).
The range API is pinned to [start, end), which cuts down off-by-one errors.
In C++ and C#, pre-validation keeps a failed overflow from leaving a partial mutation behind.
With no updates a prefix array may fit better; with many compound range operations a segment tree may.

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

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.

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