Skip to main content

BinaryIndexedTree

data-structure-typed

data-structure-typed / BinaryIndexedTree

Class: BinaryIndexedTree

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:30

Binary Indexed Tree (Fenwick Tree).

Efficient prefix sums and point updates in O(log n). Standard array-based implementation per C++ competitive programming conventions.

All indices are 0-based externally; internally converted to 1-based for BIT arithmetic.

Example​

const bit = new BinaryIndexedTree(6);
bit.update(0, 3);   // index 0 += 3
bit.update(1, 2);   // index 1 += 2
bit.update(2, 7);   // index 2 += 7

bit.query(2);       // prefix sum [0..2] = 12
bit.queryRange(1, 2); // range sum [1..2] = 9
bit.get(1);         // point value at index 1 = 2

Implements​

  • Iterable<number>

Constructors​

Constructor​

new BinaryIndexedTree(sizeOrElements): BinaryIndexedTree;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:38

Construct a BIT of given size (all zeros), or from an initial values array.

Parameters​

sizeOrElements​

number | number[]

number of elements, or an array of initial values

Returns​

BinaryIndexedTree

Methods​

[iterator]()​

iterator: IterableIterator<number>;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:634

Iterate over point values in index order.

Returns​

IterableIterator<number>

Implementation of​

Iterable.[iterator]

get()​

get(index): number;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:275

Get the point value at index (0-based). Time: O(log n)

Parameters​

index​

number

Returns​

number

Example​

// Get value at index
 const bit = new BinaryIndexedTree([1, 2, 3]);
    console.log(bit.get(0)); // 1;
    console.log(bit.get(2)); // 3;

lowerBound()​

lowerBound(sum): number;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:504

Find the smallest index i such that prefix sum [0..i] >= sum. Requires all values to be non-negative (behavior undefined otherwise). Returns size if no such index exists. Time: O(log n)

Parameters​

sum​

number

Returns​

number

Example​

// Find index with prefix sum ≥ target
 const bit = new BinaryIndexedTree([1, 2, 3, 4]);
    const idx = bit.lowerBound(4);
    console.log(idx); // >= 0;

query()​

query(index): number;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:349

Prefix sum query: returns sum of elements [0..index] (inclusive, 0-based). Time: O(log n)

Parameters​

index​

number

Returns​

number

Example​

// Prefix sum
 const bit = new BinaryIndexedTree([1, 2, 3, 4]);
    console.log(bit.query(2)); // 6;

queryRange()​

queryRange(start, end): number;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:422

Range sum query: returns sum of elements [start..end] (inclusive, 0-based). Time: O(log n)

Parameters​

start​

number

end​

number

Returns​

number

Example​

// Range sum
 const bit = new BinaryIndexedTree([1, 2, 3, 4]);
    console.log(bit.queryRange(1, 2)); // 5;

set()​

set(index, value): void;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:200

Point set: set the value at index to an absolute value (0-based). Time: O(log n)

Parameters​

index​

number

value​

number

Returns​

void

Example​

// Set value at index
 const bit = new BinaryIndexedTree([1, 2, 3]);
    bit.set(1, 10);
    console.log(bit.get(1)); // 10;

toArray()​

toArray(): number[];

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:623

Returns the point values as a plain array. Time: O(n log n)

Returns​

number[]

Example​

// Convert to array
 const bit = new BinaryIndexedTree([1, 2, 3]);
    console.log(bit.toArray()); // [1, 2, 3];

update()​

update(index, delta): void;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:125

Point update: add delta to the value at index (0-based). Time: O(log n)

Parameters​

index​

number

delta​

number

Returns​

void

Example​

// Add delta at index
 const bit = new BinaryIndexedTree([1, 2, 3, 4, 5]);
    bit.update(2, 7);
    console.log(bit.get(2)); // 10;

upperBound()​

upperBound(sum): number;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:556

Find the smallest index i such that prefix sum [0..i] > sum. Requires all values to be non-negative (behavior undefined otherwise). Returns size if no such index exists. Time: O(log n)

Parameters​

sum​

number

Returns​

number

Example​

// Find index with prefix sum > target
 const bit = new BinaryIndexedTree([1, 2, 3, 4]);
    const idx = bit.upperBound(4);
    console.log(idx); // >= 0;

Protected Members​

_highBit()​

protected _highBit(n): number;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:704

Returns highest power of 2 <= n.

Parameters​

n​

number

Returns​

number

_pointQuery()​

protected _pointQuery(pos): number;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:683

1-based point query: get exact value at pos.

Parameters​

pos​

number

Returns​

number

_pointUpdate()​

protected _pointUpdate(pos, delta): void;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:675

1-based point update: add delta to position pos.

Parameters​

pos​

number

delta​

number

Returns​

void

_prefixSum()​

protected _prefixSum(pos): number;

Defined in: data-structures/binary-tree/binary-indexed-tree.ts:665

1-based prefix sum up to pos (inclusive).

Parameters​

pos​

number

Returns​

number