Clean Markup

Fast Prefix Sums with a Fenwick Tree in JavaScript

Fast Prefix Sums with a Fenwick Tree in JavaScript

Calculating cumulative sums across an array is trivial when the data never changes: a single prefix-sum array answers any range query in $O(1)$ time. However, as soon as elements receive frequent updates—such as live analytics counters, order-book volumes, or dynamic leaderboard scores—a static prefix-sum array breaks down because each modification forces an $O(n)$ rebuild of downstream totals. Conversely, storing raw values keeps updates at $O(1)$ while degrading range sum queries to $O(n)$.

A Fenwick Tree, also known as a Binary Indexed Tree (BIT), bridges that gap by achieving both point updates and prefix-sum queries in $O(\log n)$ time using only a flat, $O(n)$-sized array. Instead of storing full cumulative sums or building pointer-heavy segment tree nodes, each 1-indexed slot tree[i] aggregates a power-of-two block whose length equals the lowest set bit of i, isolated cleanly with the bitwise expression i & -i. Backed by a Float64Array or Int32Array in JavaScript, a Fenwick Tree delivers compact memory layout, zero garbage-collection churn, and sub-millisecond performance over hundreds of thousands of entries.

Example

class FenwickTree {
  constructor(size) {
    this.size = size;
    // 1-based indexing simplifies lowest-set-bit arithmetic
    this.tree = new Float64Array(size + 1);
  }

  add(index, delta) {
    for (let i = index + 1; i <= this.size; i += i & -i) {
      this.tree[i] += delta;
    }
  }

  prefixSum(index) {
    let total = 0;
    for (let i = index + 1; i > 0; i -= i & -i) {
      total += this.tree[i];
    }
    return total;
  }

  rangeSum(left, right) {
    if (left > right) return 0;
    return this.prefixSum(right) - (left > 0 ? this.prefixSum(left - 1) : 0);
  }
}

Implementation

/**
 * Binary Indexed Tree (Fenwick Tree) backed by a TypedArray.
 * Supports O(n) initial build, O(log n) point updates, O(log n) range queries,
 * and O(log n) prefix lower-bound search for non-negative values.
 */
export class FenwickTree {
  #size;
  #tree;

  /**
   * @param {number | ArrayLike<number>} source - Length or initial numeric array
   */
  constructor(source) {
    if (typeof source === 'number') {
      if (!Number.isInteger(source) || source < 0) {
        throw new RangeError('FenwickTree size must be a non-negative integer.');
      }
      this.#size = source;
      this.#tree = new Float64Array(source + 1);
      return;
    }

    const length = source.length;
    this.#size = length;
    this.#tree = new Float64Array(length + 1);

    // Linear-time O(n) bottom-up construction
    for (let i = 0; i < length; i += 1) {
      this.#tree[i + 1] += source[i];
      const parent = i + 1 + ((i + 1) & -(i + 1));
      if (parent <= length) {
        this.#tree[parent] += this.#tree[i + 1];
      }
    }
  }

  get length() {
    return this.#size;
  }

  /**
   * Adds delta to the element at 0-based index in O(log n) time.
   */
  add(index, delta) {
    this.#assertIndex(index);
    for (let i = index + 1; i <= this.#size; i += i & -i) {
      this.#tree[i] += delta;
    }
  }

  /**
   * Sets the element at 0-based index to a specific value in O(log n) time.
   */
  set(index, value) {
    const current = this.get(index);
    this.add(index, value - current);
  }

  /**
   * Returns the single element value at 0-based index in O(log n) time.
   */
  get(index) {
    this.#assertIndex(index);
    return this.rangeSum(index, index);
  }

  /**
   * Returns the inclusive prefix sum over [0..index] in O(log n) time.
   */
  prefixSum(index) {
    this.#assertIndex(index);
    let sum = 0;
    for (let i = index + 1; i > 0; i -= i & -i) {
      sum += this.#tree[i];
    }
    return sum;
  }

  /**
   * Returns the inclusive range sum over [left..right] in O(log n) time.
   */
  rangeSum(left, right) {
    this.#assertIndex(left);
    this.#assertIndex(right);
    if (left > right) return 0;
    return this.prefixSum(right) - (left > 0 ? this.prefixSum(left - 1) : 0);
  }

  /**
   * Finds the smallest 0-based index whose prefix sum is >= target
   * using binary lifting in O(log n) time (requires non-negative values).
   */
  lowerBound(target) {
    if (target <= 0) return 0;

    let idx = 0;
    let accumulated = 0;
    let bitMask = 1 << Math.floor(Math.log2(Math.max(1, this.#size)));

    while (bitMask > 0) {
      const next = idx + bitMask;
      if (next <= this.#size && accumulated + this.#tree[next] < target) {
        idx = next;
        accumulated += this.#tree[next];
      }
      bitMask >>= 1;
    }

    return idx < this.#size ? idx : -1;
  }

  #assertIndex(index) {
    if (!Number.isInteger(index) || index < 0 || index >= this.#size) {
      throw new RangeError(`Index ${index} is out of bounds [0, ${this.#size - 1}].`);
    }
  }
}

Main Point: A Fenwick Tree stores partial power-of-two aggregates in a flat TypedArray, enabling both point updates and cumulative range queries in logarithmic time with minimal memory overhead.

Credits

Photo by Bernard Hermant on Unsplash

← Home