inordersegmenttree.md

dastal - v5.0.0 / InOrderSegmentTree

Class: InOrderSegmentTree<T>

An InOrderSegmentTree is a SegmentTree that's internally represented as a binary tree within an array, with nodes stored in in-order traversal. The tree's leaf nodes represent the elements of the segment tree:

A look at performance and how it works can be found here.

Type parameters

Name
T

Implements

• SegmentTree<T>

Table of contents

Constructors

• constructor

Accessors

• size

Methods

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

Constructors

constructor

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

Construct a new segment tree

Type parameters

Name
T

Parameters

Name	Type	Default value	Description
combine	CombineFn<T, T>	undefined	The function used to aggregate segment information
elements	Iterable<T>	[]	A set of elements to add into the initial tree

Defined in

src/segmentTree/inOrderSegmentTree.ts:21

Accessors

size

• get size(): number

The number of elements in the collection.

Returns

number

Implementation of

SegmentTree.size

Defined in

src/segmentTree/inOrderSegmentTree.ts:95

Methods

[iterator]

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

Return an iterator through the tree's elements

Returns

Iterator<T, any, undefined>

Implementation of

SegmentTree.[iterator]

Defined in

src/segmentTree/inOrderSegmentTree.ts:102

---

clear

▸ clear(): void

Removes all elements.

Returns

void

Implementation of

SegmentTree.clear

Defined in

src/segmentTree/inOrderSegmentTree.ts:36

---

pop

▸ pop(): undefined | T

Retrieves and removes the last element

Returns

undefined | T

Implementation of

SegmentTree.pop

Defined in

src/segmentTree/inOrderSegmentTree.ts:40

---

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/inOrderSegmentTree.ts:52

---

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/inOrderSegmentTree.ts:69

---

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/inOrderSegmentTree.ts:108