úÎBő<       !"#$%&'()*+, !"#$%&'(  !"#$%&'( -./-- 0123456702457024557 A function of type  a is used as if it were (8) for comparison purposes. 9:;< 024579:;<9:;< =>?@ABCDEFGHIJ)*+, !"#$%&'(=>?@ABCDFGHIJ =>?@ABCDFGHIJ KLMNOPQRSKLMNOPQSKLLMNOPQSTTTUVWUVWUVWXXXYZ[I is used as a node identifier, so that the user can refer to tree nodes  in a random-access fashion. \]Y\]Y\] ^_`aA a3 is a tree, specified in the following format: the  i-th entry of the vector is the parent of node i, or is -1 for the  root. bcO(n)H. Given a comparison function and a vector, this function constructs a  d e2 with the property that the minimum index between i and j ? in the result vector is the same as the minimum index between i and j in the P original vector. (In both cases, ties are broken by which index comes first.) BThis allows us to use the specialized range-min implementation on d e,  even for other += implementations, other element types, and other comparison  functions. MInternally, this function constructs the Cartesian tree of the input vector N (implicitly, to save memory and stack space), and returns the vector of the $ depth of each element in the tree. fFThis method takes as input a tree, specified as an array in which the  ith entry is the parent of node i, or -1 for the root. It returns ( the vector of the depths of each node. g8This method constructs the cartesian tree of the input. hijkjjlmllnopqrs@./)*+, !"#$%&'(-024579:;<=>?@ABCDFGHIJKLMNOPQSTnopqrsnopqrstuttvwxyzzz{{{&A range min function. Given an index i and a length m, returns the  minimum element in the range i..i+m-1. |O(n)K. Returns a range-min function on the vector, under the natural ordering. + This function can be six times as fast as . The returned function does not do bounds checks. O(n)K. Returns a range-min function on the vector, under the natural ordering. + This function can be six times as fast as  . The returned function does do bounds checks. O(n)M. Returns a range-min function on the vector, under the specified ordering.  The returned function does not do bounds checks. O(n)A. Returns a range-min function on the vector, under the elements' natural ordering.  The returned function does not do bounds checks. O(n)M. Returns a range-min function on the vector, under the specified ordering.  The returned function does do bounds checks. O(n)A. Returns a range-min function on the vector, under the elements' natural ordering.  The returned function does do bounds checks.    }~€$Labels a tree in depth-first order.  ]Takes a tree and indexes it in depth-first order, returning the number of nodes, the indexed 0 tree, and the lowest common ancestor function.   n ix tree( takes a tree whose nodes are mapped by  ix to a unique index in the range 0..n-1, and returns a function N which takes two indices (corresponding to two nodes in the tree) and returns  the label of their lowest common ancestor.  This takes O(n)& preprocessing and answers queries in O(1), as it is an  application of  Data.RangeMin. !For binary trees, consider using Data.RangeMin.LCA.Binary.     ‚ƒ„ A generic binary tree. …†‡WTakes a binary tree and indexes it inorder, returning the number of nodes, the indexed 0 tree, and the lowest common ancestor function.  Similar to LCA.lowestCommonAncestor>, but optimized for binary trees. This method can reasonably % be expected to run twice as fast as lowestCommonAncestor.      ˆ  !"#$$%&'()*+,-./00123456789:;<=>?@A?BC?BD?EF GHIJHIK L L M M N N O PHQR S T U V W X Y Z [ \ ] ^ _ ` a b c d e e f g h i j k lmnopqrrstuvwvxyz?{D|}~€‚ƒ‚„…†‡ˆ‰Š‚‹vwŒŽ‚‘’“”‘•–—˜rangemin-2.1.1 Data.RangeMinData.RangeMin.LCAData.RangeMin.CartesianData.RangeMin.LCA.BinaryData.RangeMin.Common.Math Data.RangeMin.Common.CombinatorsData.RangeMin.Cartesian.STInt!Data.RangeMin.Common.Vector.UtilsData.RangeMin.Common.ST#Data.RangeMin.Common.Types.IPVectorData.RangeMin.Common.TypesData.RangeMin.Common.VectorData.RangeMin.Common.UnfData.RangeMin.Common.Unf.SliceData.RangeMin.Int.Catalan.Table%Data.RangeMin.Int.Catalan.CombinatorsData.RangeMin.LCA.IndexMData.RangeMin.Int.QuadraticData.RangeMin.Int.LinearithmicData.RangeMin.CommonData.RangeMin.Int.NearLinearData.RangeMin.Int.CatalanData.RangeMin.Int.LinearLEqIndex buildDepthsRangeMinunsafeIntRangeMin intRangeMinunsafeVecRangeMinByunsafeVecRangeMin vecRangeMinBy vecRangeMinquickLCAlowestCommonAncestorBinTreeTipquickLCABinary lcaBinarydiv'mod'bit'ceilLogintLogwordLogon<$$>STInttoSTIntrunSTInt unsafeFreezesliceMwritereadnewnewWithdropsliceminIndexstreamM!getRowvector-0.6.0.2Data.Vector.GenericstreamData.Vector.Generic.BaseMutableVectorData.Vector.Generic.MutableMVector inlineRunSTbaseGHC.STSTrunST IPMVectorIPVectorIPunzipMunzipIPM GHC.Classes<=RMtoRMrunRMonRMhintSize inlineCreate replicateM foldlRange unsafeVec enumFromNinlineUnstreaminlineUnstreamR inlineNewstreamIstreamIR inlineBuildvecunsafeBackpermute'Unf generateUnf postscanlUnf'toUnfunfoldunfoldM unfoldInto0 unfoldInto buildRowsUnfmaxLogcatalanscatalan equivClassesIndexM runIndexMgetIndex execIndexMILNil CartesianTree mapAccumSM mapAccumSData.Vector.Primitiveghc-prim GHC.TypesInt makeDepthsmakeTreeQrangeMin quadTable buildTablen2Cross nlognCross nearNCross forceBlockN2 forceNLogNforceBlockMins explicitRM:< catalanIndexcatalanIndexerinternalIntRangeMinTravDepthdfOrdertravelD unfoldBin inorderBininorderD