package Ġstructures Ċ Ċ class ĠTree 2 d ( n : ĠInt ) Ġ{ ĊĠĠĠ Ġvar Ġt : ĠArray < Tre ap . Node ?> ĊĠĠĠ Ġfun Ġquery ( x 1 : ĠInt , Ġx 2 : ĠInt , Ġy 1 : ĠInt , Ġy 2 : ĠInt ): ĠLong Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx 1 Ġ= Ġx 1 ĊĠĠĠĠĠĠĠ Ġvar Ġx 2 Ġ= Ġx 2 ĊĠĠĠĠĠĠĠ Ġvar Ġres : ĠLong Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġx 1 Ġ+= Ġt . size Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġx 2 Ġ+= Ġt . size Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x 1 Ġ<= Ġx 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x 1 Ġand Ġ 1 Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtre ap And Result : ĠTre ap . Tre ap And Result Ġ= ĠTre ap . query ( t [ x 1 ], Ġy 1 . to Long (), Ġy 2 . to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt [ x 1 ] Ġ= Ġtre ap And Result . tre ap ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġres Ġ+= Ġtre ap And Result . sum ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x 2 Ġand Ġ 1 Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtre ap And Result : ĠTre ap . Tre ap And Result Ġ= ĠTre ap . query ( t [ x 2 ], Ġy 1 . to Long (), Ġy 2 . to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt [ x 2 ] Ġ= Ġtre ap And Result . tre ap ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġres Ġ+= Ġtre ap And Result . sum ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġx 1 Ġ+ Ġ 1 Ġshr Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 2 Ġ= Ġx 2 Ġ- Ġ 1 Ġshr Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġres ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġinsert ( x : ĠInt , Ġy : ĠInt , Ġvalue : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġx ĊĠĠĠĠĠĠĠ Ġx Ġ+= Ġt . size Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt [ x ] Ġ= ĠTre ap . insert ( t [ x ], Ġy . to Long (), Ġvalue . to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ= Ġx Ġshr Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmodify ( x 1 : ĠInt , Ġx 2 : ĠInt , Ġy 1 : ĠInt , Ġy 2 : ĠInt , Ġdelta : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx 1 Ġ= Ġx 1 ĊĠĠĠĠĠĠĠ Ġvar Ġx 2 Ġ= Ġx 2 ĊĠĠĠĠĠĠĠ Ġx 1 Ġ+= Ġt . size Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġx 2 Ġ+= Ġt . size Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x 1 Ġ<= Ġx 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x 1 Ġand Ġ 1 Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt [ x 1 ] Ġ= ĠTre ap . modify ( t [ x 1 ], Ġy 1 . to Long (), Ġy 2 . to Long (), Ġdelta . to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x 2 Ġand Ġ 1 Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt [ x 2 ] Ġ= ĠTre ap . modify ( t [ x 2 ], Ġy 1 . to Long (), Ġy 2 . to Long (), Ġdelta . to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġx 1 Ġ+ Ġ 1 Ġshr Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 2 Ġ= Ġx 2 Ġ- Ġ 1 Ġshr Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠUsage Ġexample ĊĠĠĠĠĠĠĠ Ġfun Ġmain ( args : ĠArray < String ?> ?) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt Ġ= ĠTree 2 d ( 1 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt . insert ( 1 , Ġ 5 , Ġ 3 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt . insert ( 3 , Ġ 3 , Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt . insert ( 2 , Ġ 6 , Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt . modify ( 0 , Ġ 9 , Ġ 0 , Ġ 9 , Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠSystem . out . println ( t . query ( 0 , Ġ 9 , Ġ 0 , Ġ 9 )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġt Ġ= ĠarrayOf Null s < Tre ap . Node >( 2 Ġ* Ġn ) ĊĠĠĠ Ġ} Ċ } Ċ