Class SegmentTree
 Object

 edu.princeton.cs.algs4.SegmentTree

public class SegmentTree extends Object
TheSegmentTree
class is an structure for efficient search of cummulative data. It performs Range Minimum Query and Range Sum Query in O(log(n)) time. It can be easily customizable to support Range Max Query, Range Multiplication Query etc.Also it has been develop with
LazyPropagation
for range updates, which means when you perform update operations over a range, the update process affects the least nodes as possible so that the bigger the range you want to update the less time it consumes to update it. Eventually those changes will be propagated to the children and the whole array will be up to date.Example:
SegmentTreeHeap st = new SegmentTreeHeap(new Integer[]{1,3,4,2,1, 2, 4}); st.update(0,3, 1) In the above case only the node that represents the range [0,3] will be updated (and not their children) so in this case the update task will be less than n*log(n) Memory usage: O(n)
 Author:
 Ricardo Pacheco


Constructor Summary
Constructors Constructor Description SegmentTree(int[] array)
TimeComplexity: O(n*log(n))

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static void
main(String[] args)
Read the following commands: init n v Initializes the array of size n with all v's set a b c...int
rMinQ(int from, int to)
Range Min Query TimeComplexity: O(log(n))int
rsq(int from, int to)
Range Sum Query TimeComplexity: O(log(n))int
size()
void
update(int from, int to, int value)
Range Update Operation.



Method Detail

size
public int size()

rsq
public int rsq(int from, int to)
Range Sum Query TimeComplexity: O(log(n)) Parameters:
from
 from indexto
 to index Returns:
 sum

rMinQ
public int rMinQ(int from, int to)
Range Min Query TimeComplexity: O(log(n)) Parameters:
from
 from indexto
 to index Returns:
 min

update
public void update(int from, int to, int value)
Range Update Operation. With this operation you can update either one position or a range of positions with a given number. The update operations will update the less it can to update the whole range (Lazy Propagation). The values will be propagated lazily from top to bottom of the segment tree. This behavior is really useful for updates on portions of the arrayTimeComplexity: O(log(n))
 Parameters:
from
 from indexto
 to indexvalue
 value

main
public static void main(String[] args)
Read the following commands: init n v Initializes the array of size n with all v's set a b c... Initializes the array with [a, b, c ...] rsq a b Range Sum Query for the range [a, b] rmq a b Range Min Query for the range [a, b] up a b v Update the [a,b] portion of the array with value v. exitExample: init set 1 2 3 4 5 6 rsq 1 3 Sum from 1 to 3 = 6 rmq 1 3 Min from 1 to 3 = 1 input up 1 3 [3,2,3,4,5,6]
 Parameters:
args
 the commandline arguments

