@algorithm.ts/binary-index-tree
v4.0.0
Published
Binary Index Tree
Downloads
60
Maintainers
Readme
A typescript implementation of the Binary Index Tree.
The Binary Index Tree is a tree-shaped array structure used to efficiently maintain the prefix sum. There are usually two modes of operation:
Single point update, interval query. Modify the value of an element in the number sequence, and solve the prefix sum at a certain position. Solve the sum of any interval $[L, R]$ can be divided into the sum of interval $[1,R]$ and the sum of interval $[1, L-1]$, then perform a subtraction operation.
Interval update, single-point query. Add a value to the value of the first $x$ elements in the sequence, and solve the current value of the element at any position in the sequence. Similarly, if you want to add a common value $x$ to any interval $[L, R]$, you can first add $x$ to all elements in [1,R], and then add $-x$ to all elements in [1,L-1].
The above operations are all done under the amortized complexity of $O(\log N)$.
The problem that the Binary Index Tree can solve is a subset of the Segment Tree. But the complexity constant of Binary Index Tree is smaller, and its implementation is simpler and easier to understand.
Install
npm
npm install --save @algorithm.ts/binary-index-tree
yarn
yarn add @algorithm.ts/binary-index-tree
Usage
Single-point update And interval query
Solve numbers:
import { SingleUpdateIntervalQuery } from '@algorithm.ts/binary-index-tree' const MAX_N = 10 const bit = new SingleUpdateIntervalQuery<number>({ operator: { ZERO: 0, add: (x, y) => x + y } }) bit.init(MAX_N) // Add 10 on the 2th element. bit.add(2, 10) // Get the prefix sums. bit.query(1) // => 0 bit.query(2) // => 10 bit.query(/* any integer between [2, 10] */) // => 10 // Add 7 on the 4th element. bit.add(4, 7) // Get the prefix sums. bit.query(1) // => 0 bit.query(2) // => 10 bit.query(3) // => 10 bit.query(4) // => 17 bit.query(/* any integer between [4, 10] */) // => 17
Solve bigint:
import { SingleUpdateIntervalQuery } from '@algorithm.ts/binary-index-tree' const MAX_N = 10 const bit = new SingleUpdateIntervalQuery<bigint>({ operator: { ZERO: 0n, add: (x, y) => x + y } }) bit.init(MAX_N) // Add 10n on the 2th element. bit.add(2, 10n) // Get the prefix sums. bit.query(1) // => 0n bit.query(2) // => 10n bit.query(/* any integer between [2, 10] */) // => 10n // Add 7n on the 4th element. bit.add(4, 7) // Get the prefix sums. bit.query(1) // => 0n bit.query(2) // => 10n bit.query(3) // => 10n bit.query(4) // => 17n bit.query(/* any integer between [4, 10] */) // => 17n
Interval update and single-point query
Solve numbers:
import { IntervalUpdateSingleQuery } from '@algorithm.ts/binary-index-tree' const MAX_N = 10 const bit = new IntervalUpdateSingleQuery<number>({ operator: { ZERO: 0, add: (x, y) => x + y } }) bit.init(MAX_N) // Add 10 on the first two elements. bit.add(2, 10) // Get the value of x-st element. bit.query(1) // => 10 bit.query(2) // => 10 bit.query(/* any integer between [3, 10] */) // => 0 // Add 7 on the first four elements. bit.add(4, 7) // Get the value of x-st element. bit.query(1) // => 17 bit.query(2) // => 17 bit.query(3) // => 17 bit.query(4) // => 17 bit.query(/* any integer between [5, 10] */) // => 0
Solve bigint:
import { IntervalUpdateSingleQuery } from '@algorithm.ts/binary-index-tree' const MAX_N = 10 const bit = new IntervalUpdateSingleQuery<number>({ operator: { ZERO: 0n, add: (x, y) => x + y } }) bit.init(MAX_N) // Add 10 on the first two elements. bit.add(2, 10n) // Get the value of x-st element. bit.query(1) // => 10n bit.query(2) // => 10n bit.query(/* any integer between [3, 10] */) // => 0n // Add 7 on the first four elements. bit.add(4, 7) // Get the value of x-st element. bit.query(1) // => 17n bit.query(2) // => 17n bit.query(3) // => 17n bit.query(4) // => 17n bit.query(/* any integer between [5, 10] */) // => 0n
With Mod
import { SingleUpdateIntervalQuery } from '@algorithm.ts/binary-index-tree' const MOD = 1e9 + 7 const bit = SingleUpdateIntervalQuery<number>({ operator: { ZERO: 0, add: (x, y) => { const z = x + y return z >= MOD ? z - MOD : z < 0 ? z + MOD : z }, }, }) bit.init(1e5 + 10) bit.add(2, <value>) // <value> should in the range of (-MOD, MOD) bit.query(3)
import { IntervalUpdateSingleQuery } from '@algorithm.ts/binary-index-tree' const MOD = BigInt(1e9 + 7) const bit = new IntervalUpdateSingleQuery<bigint>({ operator: { ZERO: 0n, add: (x, y) => { const z = x + y return z >= MOD ? z - MOD : z < 0n ? z + MOD : z }, }, }) bit.init(1e5 + 10) bit.add(2, <value>) // <value> should in the range of (-MOD, MOD) bit.query(3)