
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