segment-tree

Segment tree data structure

npm install segment-tree
12 downloads in the last week
29 downloads in the last month

segment-tree

A minimal implementation of a segment tree for storing run-length encoded arrays with updates.

Example

var tree = require("segment-tree").zeros(10)

tree.set(1, 1)
tree.set(2, 1)

console.log(tree.length)
console.log(tree.pointers)
console.log(tree.values)

Install

npm install segment-tree

API

var SegmentTree = require("segment-tree")

SegmentTree(length, pointers, values)

SegmentTree constructor

  • length is the size of the segment tree
  • pointers is a sorted list of pointers
  • values is a sorted list of values

The segment tree object has the same properties as the arguments.

SegmentTree.proto.get(index)

Retrieves the value index

  • index is the coordinate of the value to retrieve

Returns The value at index

SegmentTree.proto.set(index, v)

Sets the value at index to v

  • index is the index to update
  • v is the new value

Returns v

SegmentTree.proto.slice(begin[, end])

Returns a slice of the segment tree. Same semantics as Array.slice

  • begin is the start of the interval
  • end is the end of the interval

Returns A 1-level deep slice of the segment tree

SegmentTree.proto.toArray([array])

Unpacks the segment tree into an array

  • array gets the output. If not specified a new array is allocated

Returns array

SegmentTree.zeros(size)

Create an empty segment tree

  • size is the size of the new segment tree

Returns A new segment tree

SegmentTree.fromArray(array)

Encodes an array into a segment tree

  • array is the array to encode

Returns A new segment tree encoding array

SegmentTree.fromGenericArray(array)

Encodes an array into a segment tree, except instead of using [] to access the array it uses .get()

  • array is the array to encode

Returns A new segment tree encoding array

Credits

(c) 2013 Mikola Lysenko. MIT License

npm loves you