SegmentTree

This library implements segment tree data structure

Segment tree allows effectively calculate sum of elements in sub arrays by storing some amount of additional data.

Provided implementation assumes that arrays is indexed from 1 to n. Size of initial array always must be power of 2

Example:

Array: ------------------------+ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ------------------------+

Segment tree structure: ------------------------------- | 36 | ------------------------------+ | 10 | 26 | ----------------------------+ | 3 | 7 | 11 | 15 | ------------------------+ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ------------------------+

How the segment tree is stored in an array: -------------------------------------------------- | 36 | 10 | 26 | 3 | 7 | 11 | 15 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | --------------------------------------------------

Functions

create create(struct SegmentTree.Tree segmentTree, uint256 size) external

Allocates storage for segment tree of size elements

Requirements:

  • size must be greater than 0

  • size must be power of 2

addToPlace addToPlace(struct SegmentTree.Tree self, uint256 place, uint256 delta) external

Adds delta to element of segment tree at place

Requirements:

  • place must be in range [1, size]

removeFromPlace removeFromPlace(struct SegmentTree.Tree self, uint256 place, uint256 delta) external

Subtracts delta from element of segment tree at place

Requirements:

  • place must be in range [1, size]

  • initial value of target element must be not less than delta

moveFromPlaceToPlace moveFromPlaceToPlace(struct SegmentTree.Tree self, uint256 fromPlace, uint256 toPlace, uint256 delta) external

Adds delta to element of segment tree at toPlace and subtracts delta from element at fromPlace

Requirements:

  • fromPlace must be in range [1, size]

  • toPlace must be in range [1, size]

  • initial value of element at fromPlace must be not less than delta

getRandomNonZeroElementFromPlaceToLast getRandomNonZeroElementFromPlaceToLast(struct SegmentTree.Tree self, uint256 place, struct Random.RandomGenerator randomGenerator) → uint256 external

Returns random position in range [place, size] with probability proportional to value stored at this position. If all element in range are 0 returns 0

Requirements:

  • place must be in range [1, size]

sumFromPlaceToLast sumFromPlaceToLast(struct SegmentTree.Tree self, uint256 place) → uint256 sum public

Returns sum of elements in range [place, size]

Requirements:

  • place must be in range [1, size]

getSize getSize(struct SegmentTree.Tree segmentTree) → uint256 internal

Returns amount of elements in segment tree

Edit on Github