Class 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 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