package Ġstructures Ċ Ċ import Ġjava . util . function . Predicate Ċ Ċ // Ġhttps :// cp - algorithms . com / data _ structures / tre ap . html Ċ object ĠTre ap Indexed Ġ{ ĊĠĠĠ Ġvar Ġrandom : ĠRandom Ġ= ĠRandom () ĊĠĠĠ Ġfun Ġsplit ( root : ĠNode ?, Ġmin Right : ĠInt ): ĠTre ap Pair Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) Ġreturn ĠTre ap Pair ( null , Ġnull ) ĊĠĠĠĠĠĠĠ Ġroot . push () ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( Node . getSize ( root . left ) Ġ>= Ġmin Right ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsub Ġ= Ġsplit ( root . left , Ġmin Right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot . left Ġ= Ġsub . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot . pull () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsub . right Ġ= Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsub ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsub Ġ= Ġsplit ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot . right , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin Right Ġ- ĠNode . getSize ( root . left ) Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot . right Ġ= Ġsub . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot . pull () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsub . left Ġ= Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsub ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmerge ( left : ĠNode ?, Ġright : ĠNode ?): ĠNode ? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( left Ġ== Ġnull ) Ġreturn Ġright ĊĠĠĠĠĠĠĠ Ġif Ġ( right Ġ== Ġnull ) Ġreturn Ġleft ĊĠĠĠĠĠĠĠ Ġleft . push () ĊĠĠĠĠĠĠĠ Ġright . push () ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( left . prio Ġ> Ġright . prio ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft . right Ġ= Ġmerge ( left . right , Ġright ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft . pull () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright . left Ġ= Ġmerge ( left , Ġright . left ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright . pull () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġinsert ( root : ĠNode ?, Ġindex : ĠInt , Ġvalue : ĠLong ): ĠNode ? Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġsplit ( root , Ġindex ) ĊĠĠĠĠĠĠĠ Ġreturn Ġmerge ( merge ( t . left , ĠNode ( value )), Ġt . right ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġremove ( root : ĠNode ?, Ġindex : ĠInt ): ĠNode ? Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġsplit ( root , Ġindex ) ĊĠĠĠĠĠĠĠ Ġreturn Ġmerge ( t . left , Ġsplit ( t . right , Ġindex Ġ+ Ġ 1 Ġ- ĠNode . getSize ( t . left )). right ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmodify ( root : ĠNode ?, Ġll : ĠInt , Ġrr : ĠInt , Ġdelta : ĠLong ): ĠNode ? Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġt 1 Ġ= Ġsplit ( root , Ġrr Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġval Ġt 2 Ġ= Ġsplit ( t 1 . left , Ġll ) ĊĠĠĠĠĠĠĠ Ġif Ġ( t 2 . right Ġ!= Ġnull ) Ġt 2 . right !!. apply ( delta ) ĊĠĠĠĠĠĠĠ Ġreturn Ġmerge ( merge ( t 2 . left , Ġt 2 . right ), Ġt 1 . right ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġquery ( root : ĠNode ?, Ġll : ĠInt , Ġrr : ĠInt ): ĠTre ap And Result Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġt 1 Ġ= Ġsplit ( root , Ġrr Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġval Ġt 2 Ġ= Ġsplit ( t 1 . left , Ġll ) ĊĠĠĠĠĠĠĠ Ġval Ġmx Ġ= ĠNode . getM x ( t 2 . right ) ĊĠĠĠĠĠĠĠ Ġval Ġsum Ġ= ĠNode . get Sum ( t 2 . right ) ĊĠĠĠĠĠĠĠ Ġreturn ĠTre ap And Result ( merge ( merge ( t 2 . left , Ġt 2 . right ), Ġt 1 . right ), Ġmx , Ġsum ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġcalls Ġall ĠFALSE Ġelements Ġto Ġthe Ġleft Ġof Ġthe Ġs ought Ġposition Ġexactly Ġonce ĊĠĠĠ Ġfun Ġfind First ( root : ĠNode ?, Ġll : ĠInt , Ġrr : ĠInt , Ġf : ĠPredicate < Node ?> ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġfind First ( root , Ġll , Ġrr , Ġf , Ġ 0 , ĠNode . getSize ( root ) Ġ- Ġ 1 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġfind First ( root : ĠNode ?, Ġll : ĠInt , Ġrr : ĠInt , Ġf : ĠPredicate < Node ? >, Ġl : ĠInt , Ġr : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( ll Ġ<= Ġl Ġ&& Ġr Ġ<= Ġrr Ġ&& Ġ! f . test ( root )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( l Ġ== Ġr ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġl ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġroot !!. push () ĊĠĠĠĠĠĠĠ Ġval Ġm Ġ= ĠNode . getSize ( root . left ) ĊĠĠĠĠĠĠĠ Ġvar Ġres Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( ll Ġ< Ġm ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġres Ġ= Ġfind First ( root . left , Ġll , Ġrr , Ġf , Ġl , Ġl Ġ+ Ġm Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( res Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsingle Ġ= ĠNode ( 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsingle . size Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsingle . apply ( root . node Value ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġres Ġ= Ġfind First ( single , Ġll , Ġrr , Ġf , Ġl Ġ+ Ġm , Ġl Ġ+ Ġm ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( rr Ġ> Ġm Ġ&& Ġres Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġres Ġ= Ġfind First ( root . right , Ġll , Ġrr , Ġf , Ġl Ġ+ Ġm Ġ+ Ġ 1 , Ġr ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġroot . pull () ĊĠĠĠĠĠĠĠ Ġreturn Ġres ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġprint ( root : ĠNode ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) Ġreturn ĊĠĠĠĠĠĠĠ Ġroot . push () ĊĠĠĠĠĠĠĠ Ġprint ( root . left ) ĊĠĠĠĠĠĠĠ ĠSystem . out . print ( root . node Value . toString () Ġ+ Ġ" Ġ") ĊĠĠĠĠĠĠĠ Ġprint ( root . right ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠReturns Ġmin ( p Ġ| Ġp <= rr Ġ&& Ġsum [ ll .. p ] >= sum ). ĠIf Ġno Ġsuch Ġp Ġexists , Ġreturns Ġ- 1 ĊĠĠĠ Ġfun Ġsum Lower Bound ( tre ap : ĠNode ?, Ġll : ĠInt , Ġrr : ĠInt , Ġsum : ĠLong ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsum So Far Ġ= ĠLong Array ( 1 ) ĊĠĠĠĠĠĠĠ Ġreturn Ġfind First ( tre ap , Ġll , Ġrr , ĠPredicate < Node > Ġ{ Ġnode Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( sum So Far [ 0 ] Ġ+ Ġnode . sum Ġ>= Ġsum ) Ġreturn @ findFirst Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum So Far [ 0 ] Ġ+= Ġnode . sum ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfalse ĊĠĠĠĠĠĠĠ Ġ}) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠRandom Ġtest ĊĠĠĠ Ġfun Ġmain ( args : ĠArray < String ?> ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġtre ap : ĠNode ? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġval Ġlist : ĠList < Integer > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġval Ġrnd Ġ= ĠRandom ( 1 ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( step Ġin Ġ 0 .. 9 9 9 9 9 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcmd : ĠInt Ġ= Ġrnd . nextInt ( 6 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cmd Ġ< Ġ 2 Ġ&& Ġlist . size () Ġ< Ġ 1 0 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpos : ĠInt Ġ= Ġrnd . nextInt ( list . size () Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvalue : ĠInt Ġ= Ġrnd . nextInt ( 1 0 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlist . add ( pos , Ġvalue ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtre ap Ġ= Ġinsert ( tre ap , Ġpos , Ġvalue . to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( cmd Ġ< Ġ 3 Ġ&& Ġlist . size () Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpos : ĠInt Ġ= Ġrnd . nextInt ( list . size ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlist . remove ( pos ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtre ap Ġ= Ġremove ( tre ap , Ġpos ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( cmd Ġ< Ġ 4 Ġ&& Ġlist . size () Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb : ĠInt Ġ= Ġrnd . nextInt ( list . size ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa : ĠInt Ġ= Ġrnd . nextInt ( b Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġres : ĠInt Ġ= Ġlist [ a ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġa Ġ+ Ġ 1 .. b ) Ġres Ġ= ĠMath . max ( res , Ġlist [ i ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtr Ġ= Ġquery ( tre ap , Ġa , Ġb ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtre ap Ġ= Ġtr . tre ap ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( res . to Long () Ġ!= Ġtr . mx ) Ġthrow ĠRuntimeException () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( cmd Ġ< Ġ 5 Ġ&& Ġlist . size () Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb : ĠInt Ġ= Ġrnd . nextInt ( list . size ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa : ĠInt Ġ= Ġrnd . nextInt ( b Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdelta : ĠInt Ġ= Ġrnd . nextInt ( 1 0 0 ) Ġ- Ġ 5 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġa .. b ) Ġlist . set ( i , Ġlist [ i ] Ġ+ Ġdelta ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtre ap Ġ= Ġmodify ( tre ap , Ġa , Ġb , Ġdelta . to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġlist . size ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtr Ġ= Ġquery ( tre ap , Ġi , Ġi ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtre ap Ġ= Ġtr . tre ap ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġtr . mx ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( list [ i ] Ġ!== Ġv ) Ġthrow ĠRuntimeException () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ ĠSystem . out . println (" Test Ġpassed ") ĊĠĠĠĠĠĠĠ Ġtre ap Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġfor Ġ( v Ġin Ġlong ArrayOf ( 2 , Ġ 1 , Ġ 1 0 , Ġ 2 0 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtre ap Ġ= Ġinsert ( tre ap , ĠNode . getSize ( tre ap ), Ġv ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ ĠSystem . out . println ( 2 Ġ== Ġsum Lower Bound ( tre ap , Ġ 0 , Ġtre ap !!. size Ġ- Ġ 1 , Ġ 1 2 )) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġclass ĠNode Ġinternal Ġconstructor ( var Ġnode Value : ĠLong ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġmx : ĠLong ĊĠĠĠĠĠĠĠ Ġvar Ġsum : ĠLong ĊĠĠĠĠĠĠĠ Ġvar Ġadd : ĠLong ĊĠĠĠĠĠĠĠ Ġvar Ġsize : ĠInt ĊĠĠĠĠĠĠĠ Ġvar Ġpri o : ĠLong ĊĠĠĠĠĠĠĠ Ġvar Ġleft : ĠNode ? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġvar Ġright : ĠNode ? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġfun Ġapply ( v : ĠLong ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Value Ġ+= Ġv ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmx Ġ+= Ġv ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ+= Ġv Ġ* Ġsize ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd Ġ+= Ġv ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġpush () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( add Ġ!= Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( left Ġ!= Ġnull ) Ġleft !!. apply ( add ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( right Ġ!= Ġnull ) Ġright !!. apply ( add ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadd Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġpull () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmx Ġ= ĠMath . max ( node Value , ĠMath . max ( getM x ( left ), Ġget Mx ( right ))) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ= Ġnode Value Ġ+ Ġget Sum ( left ) Ġ+ Ġget Sum ( right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsize Ġ= Ġ 1 Ġ+ Ġget Size ( left ) Ġ+ Ġget Size ( right ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfun Ġget Mx ( root : ĠNode ?): ĠLong Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġroot ?. mx Ġ?: ĠLong . MIN _ VALUE ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfun Ġget Sum ( root : ĠNode ?): ĠLong Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġroot ?. sum Ġ?: Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfun Ġget Size ( root : ĠNode ?): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġroot ?. size Ġ?: Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmx Ġ= Ġnode Value ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ= Ġnode Value ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsize Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpri o Ġ= Ġrandom . next Long () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġclass ĠTre ap Pair Ġinternal Ġconstructor ( var Ġleft : ĠNode ?, Ġvar Ġright : ĠNode ?) ĊĠĠĠ Ġclass ĠTre ap And Result Ġinternal Ġconstructor ( var Ġtre ap : ĠNode ?, Ġvar Ġmx : ĠLong , Ġvar Ġsum : ĠLong ) Ċ } Ċ