import BinaryIndexedTree from 'binary-indexed-tree/src/bit.js'

public class | source

BinaryIndexedTree

BinaryIndexedTree implementation

Static Method Summary

Static Public Methods
public static	build(seed: Array<number>): BinaryIndexedTree

Constructor Summary

Public Constructor
public	constructor(size: number)

Member Summary

Public Members
public get	length: number: *

Method Summary

Public Methods
public	add(idx: number, val: number): boolean
public	find(check: Function): number linear search.
public	findIndex(check: Function): number linear search.
public	get(idx: number): number
public	indexOf(target: number, equal: Function): number linear search.
public	lastIndexOf(target: number, equal: Function): number linear search.
public	lowerBound(target: number, comp: Function): number find lower bound.
public	original(idx: number): number
public	prefix(idx: number): number
public	replace(idx: number, val: number): boolean
public	sum(): number
public	toArray(): Array<number>
public	upperBound(target: number, comp: Function): number find upper bound.

Static Public Methods

public static build(seed: Array<number>): BinaryIndexedTree source

Params:

Name	Type	Attribute	Description
seed	Array<number>		BIT will be built from this array

Return:

BinaryIndexedTree

instance O(N)

Public Constructors

public constructor(size: number) source

Params:

Name	Type	Attribute	Description
size	number

Public Members

public get length: number: * source

Return:

number

size of BIT

Public Methods

public add(idx: number, val: number): boolean source

Params:

Name	Type	Attribute	Description
idx	number		should be less than size of BIT
val	number

Return:

boolean

successfully added or not O(log(N))

public find(check: Function): number source

linear search.

Params:

Name	Type	Attribute	Description
check	Function		function

Return:

number

value of first target, or undefined O(N * log(N))

public findIndex(check: Function): number source

linear search.

Params:

Name	Type	Attribute	Description
check	Function		function

Return:

number

index of first target, or -1 O(N * log(N))

public get(idx: number): number source

Params:

Name	Type	Attribute	Description
idx	number		should be less than size of BIT

Return:

number

sum of range [0..idx] O(log(N))

public indexOf(target: number, equal: Function): number source

linear search.

Params:

Name	Type	Attribute	Description
target	number		value
equal	Function	optional	equality function

Return:

number

index of first target, or -1 O(N * log(N))

public lastIndexOf(target: number, equal: Function): number source

linear search.

Params:

Name	Type	Attribute	Description
target	number		value
equal	Function	optional	equality function

Return:

number

index of last target, or -1 O(N * log(N))

public lowerBound(target: number, comp: Function): number source

find lower bound. SEQUENCE SHOULD BE INCREASING IN ORDER (GIVEN BY COMPERATOR). IF ANY ITEM HAS MINUS VALUE, THIS METHOD WILL NOT WORK.

Params:

Name	Type	Attribute	Description
target	number
comp	Function	optional

Return:

number

index of lower-bound O(log(N))

public original(idx: number): number source

Params:

Name	Type	Attribute	Description
idx	number		should be less than size of BIT

Return:

number

original value of array O(log(N))

public prefix(idx: number): number source

Params:

Name	Type	Attribute	Description
idx	number		should be less than size of BIT

Return:

number

sum of range [0..idx) O(log(N))

public replace(idx: number, val: number): boolean source

Params:

Name	Type	Attribute	Description
idx	number		should be less than size of BIT
val	number

Return:

boolean

successfully replaced or not O(log(N))

public sum(): number source

Return:

number

sum of all O(log(N))

public toArray(): Array<number> source

Return:

Array<number>

array of cusum O(N)

public upperBound(target: number, comp: Function): number source

find upper bound. SEQUENCE SHOULD BE INCREASING IN ORDER (GIVEN BY COMPERATOR). IF ANY ITEM HAS MINUS VALUE, THIS METHOD WILL NOT WORK.

Params:

Name	Type	Attribute	Description
target	number
comp	Function	optional

Return:

number

index of upper-bound O(log(N))