A minimal implementation of a segment tree for storing run-length encoded arrays with updates.
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)
npm install segment-tree
var SegmentTree = require("segment-tree")
SegmentTree(length, pointers, values)
SegmentTree constructor
length
is the size of the segment treepointers
is a sorted list of pointersvalues
is a sorted list of valuesThe 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 retrieveReturns The value at index
SegmentTree.proto.set(index, v)
Sets the value at index
to v
index
is the index to updatev
is the new valueReturns v
SegmentTree.proto.slice(begin[, end])
Returns a slice of the segment tree. Same semantics as Array.slice
begin
is the start of the intervalend
is the end of the intervalReturns 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 allocatedReturns array
SegmentTree.zeros(size)
Create an empty segment tree
size
is the size of the new segment treeReturns A new segment tree
SegmentTree.fromArray(array)
Encodes an array into a segment tree
array
is the array to encodeReturns 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 encodeReturns A new segment tree encoding array
(c) 2013 Mikola Lysenko. MIT License