levelordersegmenttree.md

dastal - v5.0.0 / LevelOrderSegmentTree

Class: LevelOrderSegmentTree<T>

A SegmentTree internally represented as a binary tree within an array, with nodes stored in level-order traversal.

Memory usage: n elements require n - 1 + 2**(⌊log₂(n-1)⌋ + 1) space.

Type parameters

Name
T

Implements

• SegmentTree<T>

Table of contents

Constructors

• constructor

Accessors

• size

Methods

• [iterator]
• clear
• pop
• push
• query
• update

Constructors

constructor

• new LevelOrderSegmentTree<T>(combine, elements?)

Construct a new SegmentTree

Type parameters

Name
T

Parameters

Name	Type	Default value	Description
combine	CombineFn<T, T>	undefined	-
elements	Iterable<T>	[]	Initial elements to build into the tree

Defined in

src/segmentTree/levelOrderSegmentTree.ts:59

Accessors

size

• get size(): number

The number of elements in the collection.

Returns

number

Implementation of

SegmentTree.size

Defined in

src/segmentTree/levelOrderSegmentTree.ts:143

Methods

[iterator]

▸ [iterator](): Iterator<T, any, undefined>

Return an iterator through the elements

Returns

Iterator<T, any, undefined>

Implementation of

SegmentTree.[iterator]

Defined in

src/segmentTree/levelOrderSegmentTree.ts:150

---

clear

▸ clear(): void

Removes all elements.

Returns

void

Implementation of

SegmentTree.clear

Defined in

src/segmentTree/levelOrderSegmentTree.ts:74

---

pop

▸ pop(): undefined | T

Retrieves and removes the last element

Returns

undefined | T

Implementation of

SegmentTree.pop

Defined in

src/segmentTree/levelOrderSegmentTree.ts:80

---

push

▸ push(element): number

Appends an element to the tree

Parameters

Name	Type
element	T

Returns

number

Implementation of

SegmentTree.push

Defined in

src/segmentTree/levelOrderSegmentTree.ts:97

---

query

▸ query(min, max): T

Get the aggregated result of a given range in the tree

Parameters

Name	Type
min	number
max	number

Returns

T

Implementation of

SegmentTree.query

Defined in

src/segmentTree/levelOrderSegmentTree.ts:115

---

update

▸ update(min, max, operation): void

Update the elements of a given range in the tree

Parameters

Name	Type
min	number
max	number
operation	(element: T, index: number) => T

Returns

void

Implementation of

SegmentTree.update

Defined in

src/segmentTree/levelOrderSegmentTree.ts:156