edu.princeton.cs.algs4

Class SegmentTree

Object

edu.princeton.cs.algs4.SegmentTree

public class SegmentTree
extends Object

The SegmentTree 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 and Description
SegmentTree(int[] array) Time-Complexity: O(n*log(n))

Method Summary

Modifier and Type	Method and 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 Time-Complexity: O(log(n))
int	rsq(int from, int to) Range Sum Query Time-Complexity: O(log(n))
int	size()
void	update(int from, int to, int value) Range Update Operation.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SegmentTree

public SegmentTree(int[] array)

Time-Complexity: O(n*log(n))

Parameters:

array - the Initialization array

Method Detail

size

public int size()

rsq

public int rsq(int from,
               int to)

Range Sum Query Time-Complexity: O(log(n))

Parameters:

from - from index

to - to index

Returns:

sum

rMinQ

public int rMinQ(int from,
                 int to)

Range Min Query Time-Complexity: O(log(n))

Parameters:

from - from index

to - 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 array

Time-Complexity: O(log(n))

Parameters:

from - from index

to - to index

value - 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. exit

Example: 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 command-line arguments