程序包 edu.princeton.cs.algs4

类 SegmentTree

  • public class SegmentTree
extends java.lang.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)

    • 构造器概要

      构造器 
      构造器 说明
      SegmentTree​(int[] array)
      Time-Complexity: O(n*log(n))

    • 方法概要

      修饰符和类型 方法 说明
      static void main​(java.lang.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.

      • 从类继承的方法 java.lang.Object

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

    • 构造器详细资料

      • SegmentTree

        public SegmentTree​(int[] array)
        Time-Complexity: O(n*log(n))
        参数:
        array - the Initialization array

    • 方法详细资料

      • size

        public int size()

      • rsq

        public int rsq​(int from,
               int to)
        Range Sum Query Time-Complexity: O(log(n))
        参数:
        from - from index
        to - to index
        返回:
        sum

      • rMinQ

        public int rMinQ​(int from,
                 int to)
        Range Min Query Time-Complexity: O(log(n))
        参数:
        from - from index
        to - to index
        返回:
        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))

        参数:
        from - from index
        to - to index
        value - value

      • main

        public static void main​(java.lang.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]

        参数:
        args - the command-line arguments