public class SegmentTree extends Object
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)
Constructor and Description |
---|
SegmentTree(int[] array)
Time-Complexity: O(n*log(n))
|
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.
|
public SegmentTree(int[] array)
array
- the Initialization arraypublic int size()
public int rsq(int from, int to)
from
- from indexto
- to indexpublic int rMinQ(int from, int to)
from
- from indexto
- to indexpublic void update(int from, int to, int value)
Time-Complexity: O(log(n))
from
- from indexto
- to indexvalue
- valuepublic static void main(String[] args)
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]
args
- the command-line arguments