BinaryIndexedTree
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:221
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:98
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:145
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:111
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:126
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:83
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:210
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:69
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:174
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:291
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:270
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:262
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:252
1-based prefix sum up to pos (inclusive).
Parameters
pos
number
Returns
number