/* Segment tree

Segment tree is a data structure for efficient range operations on sequences.

Notes:

- A binary operation to be used may be a partial function as long as it can be
  applied to any consecutive elements in a sequence. Hence `segtree` can handle
  matrix production and range union.

Usage:

```
import ck/algebra/monoid
import ck/segtree

fun main()
  val seg = segtree(10, ?monoid=int/add/monoid)

  seg.set(1, 3, ?monoid=int/add/monoid)
  seg.set(3, 8, ?monoid=int/add/monoid)
  seg.product(0, 10, ?monoid=int/add/monoid).println // 11
```
\/
*/
module ck/segtreeck/segtree

import std/core/intstd/core/int
import std/core/undivstd/core/undiv
import ck/algebra/monoidck/algebra/monoid
import ck/mathck/math

abstract value struct segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>
  prodck/segtree/segtree/prod: forall<h,a> (segtree : segtree<h,a>) -> ref<h,vector<a>> : refstd/core/types/ref: (H, V) -> V<hh: H,vectorstd/core/types/vector: V -> V<aa: V>>
  leaf-countck/segtree/segtree/leaf-count: forall<h,a> (segtree : segtree<h,a>) -> int : intstd/core/types/int: V

// Create a segment tree
pub inline fun segtreeck/segtree/segtree: forall<a,h> (n : int, @implicit/monoid : monoid<a>) -> (alloc<h>) segtree<h,a>(nn: int: intstd/core/types/int: V, @implicit/monoid?monoid: monoid<$321>: monoidck/algebra/monoid/monoid: V -> V<aa: V>)result: -> (alloc<378>) segtree<378,377>: allocstd/core/types/alloc: H -> X<hh: H> segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>
  Segtreeck/segtree/Segtree: forall<h,a> (prod : ref<h,vector<a>>, leaf-count : int) -> segtree<h,a>(
    refstd/core/types/ref: (value : vector<$321>) -> (alloc<$322>) ref<$322,vector<$321>>(vectorstd/core/vector/vector: (n : int, default : $321) -> (alloc<$322>) vector<$321>(nn: int *std/core/int/(*): (int, int) -> (alloc<$322>) int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010, @implicit/monoid?monoid: monoid<$321>.oneck/algebra/monoid/monoid/one: (monoid : monoid<$321>) -> (alloc<$322>) $321)),
    nn: int
  )

// Note: `@unsafe-vector` is introduced in Koka v3.1.3.

// Unsafe function.
// This function is an internal function in the standard library.
// See <https://koka-lang.github.io/koka/doc/std_core_vector.html>
inline extern unsafe-vectorck/segtree/unsafe-vector: forall<a> (n : ssize_t) -> vector<a>(n: ssize_tstd/core/types/ssize_t: V): totalstd/core/types/total: E vectorstd/core/types/vector: V -> V<aa: V>
  c inline "kk_vector_alloc(#1, kk_box_null(), kk_context())"

pub fun list/segtreeck/segtree/list/segtree: forall<a,h> (l : list<a>, @implicit/monoid : monoid<a>) -> <alloc<h>,div,exn> segtree<h,a>(ll: list<$491>: liststd/core/types/list: V -> V<aa: V>, @implicit/monoid?monoid: monoid<$491>: monoidck/algebra/monoid/monoid: V -> V<aa: V>)result: -> <alloc<862>,div,exn> segtree<862,861>: <std/core/types/total: Eallocstd/core/types/alloc: H -> X<hh: H>,divstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V> segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>
  val nn: int = ll: list<$491>.lengthstd/core/list/length: (xs : list<$491>) -> <alloc<$492>,exn,local<$502>,div> int
  var prodprod: local-var<$502,vector<$491>> := unsafe-vectorck/segtree/unsafe-vector: (n : ssize_t) -> <alloc<$492>,exn,local<$502>,div> vector<$491>((nn: int *std/core/int/(*): (int, int) -> <alloc<$492>,exn,local<$502>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010).ssize_tstd/core/int/ssize_t: (i : int) -> <alloc<$492>,exn,local<$502>,div> ssize_t)
  ll: list<$491>.foreach-indexedstd/core/list/foreach-indexed: (xs : list<$491>, action : (int, $491) -> <exn,local<$502>,alloc<$492>,div> ()) -> <exn,local<$502>,alloc<$492>,div> () fnfn: (i : int, v : $491) -> <exn,local<$502>,alloc<$492>,div> ()(ii: int, vv: $491)
    prodprod: local-var<$502,vector<$491>>[ii: int +std/core/int/(+): (x : int, y : int) -> <exn,local<$502>,alloc<$492>,div> int nn: int] := vv: $491
  inline fun looploop: (left : int, right : int) -> <exn,local<$502>> ()(leftleft: int: intstd/core/types/int: V, rightright: int: intstd/core/types/int: V)result: -> <exn,local<$502>> ()
    if rightright: int <=std/core/int/(<=): (x : int, y : int) -> <exn,local<$502>> bool leftleft: int then returnreturn: () (std/core/types/Unit: ())std/core/types/Unit: ()
    forstd/core/range/for: (start : int, end : int, action : (int) -> <exn,local<$502>> ()) -> <exn,local<$502>> ()(leftleft: int, rightright: int -std/core/int/(-): (x : int, y : int) -> <exn,local<$502>> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) fnfn: (i : int) -> <exn,local<$502>> ()(ii: int)
      prodprod: local-var<$502,vector<$491>>[ii: int] := (@implicit/monoid?monoid: monoid<$491>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$491>) -> <exn,local<$502>> (($491, $491) -> $491))(prodprod: vector<$491>
?hdiv=iev@676[ii: int *std/core/int/(*): (int, int) -> <local<$502>,exn> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010], prodprod: vector<$491>
?hdiv=iev@719[ii: int *std/core/int/(*): (int, int) -> <local<$502>,exn> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 +std/core/int/(+): (x : int, y : int) -> <local<$502>,exn> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001])
    looploop: (left : int, right : int) -> <exn,local<$502>> ()(((leftleft: int +std/core/int/(+): (x : int, y : int) -> <exn,local<$502>> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) /std/core/int/(/): (x : int, y : int) -> <exn,local<$502>> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010).pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> <exn,local<$502>> int, rightright: int /std/core/int/(/): (x : int, y : int) -> <exn,local<$502>> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010)
  looploop: (left : int, right : int) -> <exn,local<$502>,alloc<$492>,div> ()((nn: int +std/core/int/(+): (x : int, y : int) -> <exn,local<$502>,alloc<$492>,div> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) /std/core/int/(/): (x : int, y : int) -> <exn,local<$502>,alloc<$492>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010, nn: int)
  Segtreeck/segtree/Segtree: forall<h,a> (prod : ref<h,vector<a>>, leaf-count : int) -> segtree<h,a>(refstd/core/types/ref: (value : vector<$491>) -> <alloc<$492>,local<$502>,exn,div> ref<$492,vector<$491>>(prodprod: vector<$491>
?hdiv=iev@824), nn: int)

pub fun vector/segtreeck/segtree/vector/segtree: forall<a,h> (v : vector<a>, @implicit/monoid : monoid<a>) -> <alloc<h>,div,exn> segtree<h,a>(vv: vector<$870>: vectorstd/core/types/vector: V -> V<aa: V>, @implicit/monoid?monoid: monoid<$870>: monoidck/algebra/monoid/monoid: V -> V<aa: V>)result: -> <alloc<1255>,div,exn> segtree<1255,1254>: <std/core/types/total: Eallocstd/core/types/alloc: H -> X<hh: H>,divstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V> segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>
  val nn: int = vv: vector<$870>.lengthstd/core/vector/length: (v : vector<$870>) -> <alloc<$871>,exn,local<$881>,div> int
  var prodprod: local-var<$881,vector<$870>> := unsafe-vectorck/segtree/unsafe-vector: (n : ssize_t) -> <alloc<$871>,exn,local<$881>,div> vector<$870>((nn: int *std/core/int/(*): (int, int) -> <alloc<$871>,exn,local<$881>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010).ssize_tstd/core/int/ssize_t: (i : int) -> <alloc<$871>,exn,local<$881>,div> ssize_t)
  forstd/core/for: (n : int, action : (int) -> <exn,local<$881>,alloc<$871>,div> ()) -> <exn,local<$881>,alloc<$871>,div> ()(nn: int) fnfn: (i : int) -> <exn,local<$881>,alloc<$871>,div> ()(ii: int)
    prodprod: local-var<$881,vector<$870>>[ii: int +std/core/int/(+): (x : int, y : int) -> <exn,local<$881>,alloc<$871>,div> int nn: int] := vv: vector<$870>[ii: int]
  inline fun looploop: (left : int, right : int) -> <exn,local<$881>> ()(leftleft: int: intstd/core/types/int: V, rightright: int: intstd/core/types/int: V)result: -> <exn,local<$881>> ()
    if rightright: int <=std/core/int/(<=): (x : int, y : int) -> <exn,local<$881>> bool leftleft: int then returnreturn: () (std/core/types/Unit: ())std/core/types/Unit: ()
    forstd/core/range/for: (start : int, end : int, action : (int) -> <exn,local<$881>> ()) -> <exn,local<$881>> ()(leftleft: int, rightright: int -std/core/int/(-): (x : int, y : int) -> <exn,local<$881>> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) fnfn: (i : int) -> <exn,local<$881>> ()(ii: int)
      prodprod: local-var<$881,vector<$870>>[ii: int] := (@implicit/monoid?monoid: monoid<$870>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$870>) -> <exn,local<$881>> (($870, $870) -> $870))(prodprod: vector<$870>
?hdiv=iev@1069[ii: int *std/core/int/(*): (int, int) -> <local<$881>,exn> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010], prodprod: vector<$870>
?hdiv=iev@1112[ii: int *std/core/int/(*): (int, int) -> <local<$881>,exn> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 +std/core/int/(+): (x : int, y : int) -> <local<$881>,exn> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001])
    looploop: (left : int, right : int) -> <exn,local<$881>> ()(((leftleft: int +std/core/int/(+): (x : int, y : int) -> <exn,local<$881>> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) /std/core/int/(/): (x : int, y : int) -> <exn,local<$881>> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010).pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> <exn,local<$881>> int, rightright: int /std/core/int/(/): (x : int, y : int) -> <exn,local<$881>> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010)
  looploop: (left : int, right : int) -> <exn,local<$881>,alloc<$871>,div> ()((nn: int +std/core/int/(+): (x : int, y : int) -> <exn,local<$881>,alloc<$871>,div> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) /std/core/int/(/): (x : int, y : int) -> <exn,local<$881>,alloc<$871>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010, nn: int)
  Segtreeck/segtree/Segtree: forall<h,a> (prod : ref<h,vector<a>>, leaf-count : int) -> segtree<h,a>(refstd/core/types/ref: (value : vector<$870>) -> <alloc<$871>,local<$881>,exn,div> ref<$871,vector<$870>>(prodprod: vector<$870>
?hdiv=iev@1217), nn: int)

// Get the `k`-th element.
// The first element is at position 0 (0-based).
pub inline fun @index(^segseg: segtree<$387,$386>: segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>, ^kk: int: intstd/core/types/int: V)result: -> <read<470>,div,exn> 469: <std/core/types/total: Ereadstd/core/types/read: H -> X<hh: H>,divstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V> aa: V
  (!std/core/types/ref/(!): (ref : ref<$387,vector<$386>>, @implicit/hdiv : hdiv<$387,vector<$386>,<exn,div>>) -> <read<$387>,exn,div> vector<$386>
?hdiv=iev@413segseg: segtree<$387,$386>.prodck/segtree/segtree/prod: (segtree : segtree<$387,$386>) -> <read<$387>,exn,div> ref<$387,vector<$386>>)[kk: int +std/core/int/(+): (x : int, y : int) -> <read<$387>,exn,div> int segseg: segtree<$387,$386>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$387,$386>) -> <read<$387>,exn,div> int]

inline fun recalcck/segtree/recalc: forall<a,h> (seg : segtree<h,a>, k : int, @implicit/monoid : monoid<a>) -> <read<h>,write<h>,div,exn> ()(segseg: segtree<$1264,$1263>: segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>, kk: int: intstd/core/types/int: V, @implicit/monoid?monoid: monoid<$1263>: monoidck/algebra/monoid/monoid: V -> V<aa: V>)result: -> <read<2088>,write<2088>,div,exn> (): <std/core/types/total: Ereadstd/core/types/read: H -> X<hh: H>,writestd/core/types/write: H -> X<hh: H>,divstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V> (std/core/types/unit: V)std/core/types/unit: V
  segseg: segtree<$1264,$1263>.prodck/segtree/segtree/prod: (segtree : segtree<$1264,$1263>) -> <exn,read<$1264>,write<$1264>,div> ref<$1264,vector<$1263>>.modifystd/core/types/modify: (ref : ref<$1264,vector<$1263>>, f : forall<h> (local-var<h,vector<$1263>>) -> <local<h>,exn,div> (), @implicit/hdiv : hdiv<$1264,vector<$1263>,<exn,div>>) -> <read<$1264>,write<$1264>,exn,div> ()
?hdiv=iev@1269 fnfn: forall<h> (prod : local-var<h,vector<$1263>>) -> <exn,local<h>,div> ()(prodprod: local-var<$1292,vector<$1263>>)
    inline fun looploop: (i : int, start : int, invalid-start : bool) -> <exn,local<$1292>> ()(ii: int: intstd/core/types/int: V, startstart: int: intstd/core/types/int: V, invalid-startinvalid-start: bool: boolstd/core/types/bool: V)result: -> <exn,local<$1292>> ()
      if ii: int ==std/core/int/(==): (x : int, y : int) -> <exn,local<$1292>> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000 ||std/core/types/(||): (x : bool, y : bool) -> <exn,local<$1292>> bool invalid-startinvalid-start: bool &&std/core/types/(&&): (x : bool, y : bool) -> <exn,local<$1292>> bool ii: int ==std/core/int/(==): (x : int, y : int) -> <exn,local<$1292>> bool startstart: int then
        returnreturn: () (std/core/types/Unit: ())std/core/types/Unit: ()
      prodprod: local-var<$1292,vector<$1263>>[ii: int] := (@implicit/monoid?monoid: monoid<$1263>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$1263>) -> <exn,local<$1292>> (($1263, $1263) -> $1263))(prodprod: vector<$1263>
?hdiv=iev@1596[ii: int *std/core/int/(*): (int, int) -> <local<$1292>,exn> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010], prodprod: vector<$1263>
?hdiv=iev@1639[ii: int *std/core/int/(*): (int, int) -> <local<$1292>,exn> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 +std/core/int/(+): (x : int, y : int) -> <local<$1292>,exn> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001])
      looploop: (i : int, start : int, invalid-start : bool) -> <exn,local<$1292>> ()((ii: int /std/core/int/(/): (x : int, y : int) -> <exn,local<$1292>> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010).pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> <exn,local<$1292>> int, startstart: int /std/core/int/(/): (x : int, y : int) -> <exn,local<$1292>> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010, invalid-startinvalid-start: bool ||std/core/types/(||): (x : bool, y : bool) -> <exn,local<$1292>> bool startstart: int %std/core/int/(%): (int, int) -> <exn,local<$1292>> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 ==std/core/int/(==): (x : int, y : int) -> <exn,local<$1292>> bool 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001)
    val ss: int =
      if kk: int >=std/core/int/(>=): (x : int, y : int) -> <exn,local<$1292>,div> bool segseg: segtree<$1264,$1263>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$1264,$1263>) -> <exn,local<$1292>,div> int.floor-logck/math/floor-log: (n : int, base : int) -> <exn,local<$1292>,div> int(2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010).incstd/core/int/inc: (i : int) -> <exn,local<$1292>,div> int.exp2std/core/int/exp2: (exp : int) -> <exn,local<$1292>,div> int then
        segseg: segtree<$1264,$1263>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$1264,$1263>) -> <exn,local<$1292>,div> int *std/core/int/(*): (int, int) -> <exn,local<$1292>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010
      else
        segseg: segtree<$1264,$1263>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$1264,$1263>) -> <exn,local<$1292>,div> int
    looploop: (i : int, start : int, invalid-start : bool) -> <exn,local<$1292>,div> ()(kk: int /std/core/int/(/): (x : int, y : int) -> <exn,local<$1292>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010, ss: int /std/core/int/(/): (x : int, y : int) -> <exn,local<$1292>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010, ss: int %std/core/int/(%): (int, int) -> <exn,local<$1292>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 ==std/core/int/(==): (x : int, y : int) -> <exn,local<$1292>,div> bool 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001)

// Set a value to an element.
// The first element is at position 0 (0-based).
pub fun setck/segtree/set: forall<a,h> (seg : segtree<h,a>, k : int, v : a, @implicit/monoid : monoid<a>) -> <read<h>,write<h>,div,exn> ()(segseg: segtree<$2097,$2096>: segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>, kk: int: intstd/core/types/int: V, vv: $2096: aa: V, @implicit/monoid?monoid: monoid<$2096>: monoidck/algebra/monoid/monoid: V -> V<aa: V>)result: -> <read<2255>,write<2255>,div,exn> (): <std/core/types/total: Ereadstd/core/types/read: H -> X<hh: H>,writestd/core/types/write: H -> X<hh: H>,divstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V> (std/core/types/unit: V)std/core/types/unit: V
  val k'k': int = kk: int +std/core/int/(+): (x : int, y : int) -> <div,exn,read<$2097>,write<$2097>> int segseg: segtree<$2097,$2096>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$2097,$2096>) -> <div,exn,read<$2097>,write<$2097>> int
  segseg: segtree<$2097,$2096>.prodck/segtree/segtree/prod: (segtree : segtree<$2097,$2096>) -> <exn,read<$2097>,write<$2097>,div> ref<$2097,vector<$2096>>.modifystd/core/types/modify: (ref : ref<$2097,vector<$2096>>, f : forall<h> (local-var<h,vector<$2096>>) -> <local<h>,exn,div> (), @implicit/hdiv : hdiv<$2097,vector<$2096>,<exn,div>>) -> <read<$2097>,write<$2097>,exn,div> ()
?hdiv=iev@2119 fnfn: forall<h> (prod : local-var<h,vector<$2096>>) -> <exn,local<h>,div> ()(prodprod: local-var<$2142,vector<$2096>>) { prodprod: local-var<$2142,vector<$2096>>[k'k': int] := vv: $2096 }
  segseg: segtree<$2097,$2096>.recalcck/segtree/recalc: (seg : segtree<$2097,$2096>, k : int, @implicit/monoid : monoid<$2096>) -> <div,exn,read<$2097>,write<$2097>> ()
?monoid=?monoid(k'k': int)

// Apply a function to an element.
// The first element is at position 0 (0-based).
pub fun updateck/segtree/update: forall<a,e,h> (seg : segtree<h,a>, k : int, f : forall<h1> (a) -> <read<h1>,write<h1>,div,exn|e> a, @implicit/monoid : monoid<a>) -> <read<h>,write<h>,div,exn|e> ()(
  segseg: segtree<$2265,$2263>: segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>,
  kk: int: intstd/core/types/int: V,
  ff: forall<h> ($2263) -> <read<h>,write<h>,div,exn|$2264> $2263: forall<h1h1: H> aa: V -> <readstd/core/types/read: H -> X<h1h1: H>,writestd/core/types/write: H -> X<h1h1: H>,divstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V,
  @implicit/monoid?monoid: monoid<$2263>: monoidck/algebra/monoid/monoid: V -> V<aa: V>
)result: -> <read<2390>,write<2390>,div,exn|2389> (): <readstd/core/types/read: H -> X<hh: H>,writestd/core/types/write: H -> X<hh: H>,divstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V|std/core/types/effect-extend: (X, E) -> Eee: E> (std/core/types/unit: V)std/core/types/unit: V
  segseg: segtree<$2265,$2263>.setck/segtree/set: (seg : segtree<$2265,$2263>, k : int, v : $2263, @implicit/monoid : monoid<$2263>) -> <div,exn,read<$2265>,write<$2265>|$2264> ()
?monoid=?monoid(kk: int, ff: ($2263) -> <read<$2265>,write<$2265>,div,exn|$2264> $2263(segseg: segtree<$2265,$2263>[kk: int]))

// Return the product from the `left`-th element (inclusive) to `right`-th element (exclusive).
// The first element is at position 0 (0-based).
pub fun productck/segtree/product: forall<a,h> (seg : segtree<h,a>, left : int, right : int, @implicit/monoid : monoid<a>) -> <read<h>,div,exn> a(segseg: segtree<$2402,$2401>: segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>, leftleft: int: intstd/core/types/int: V, rightright: int: intstd/core/types/int: V, @implicit/monoid?monoid: monoid<$2401>: monoidck/algebra/monoid/monoid: V -> V<aa: V>)result: -> <read<2829>,div,exn> 2828: <std/core/types/total: Ereadstd/core/types/read: H -> X<hh: H>,divstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V> aa: V
  inline fun looploop: (l : int, r : int, pl : $2401, pr : $2401) -> <pure,read<$2402>> $2401(ll: int: intstd/core/types/int: V, rr: int: intstd/core/types/int: V, plpl: $2401, prpr: $2401)result: -> <exn,read<$2402>,div> $2401
    if ll: int <std/core/int/(<): (x : int, y : int) -> <exn,read<$2402>,div> bool rr: int then
      val (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)l'l': int, pl'pl': $2401)std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b) =
        if ll: int %std/core/int/(%): (int, int) -> <exn,read<$2402>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 >std/core/int/(>): (x : int, y : int) -> <exn,read<$2402>,div> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000 then
          (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)ll: int +std/core/int/(+): (x : int, y : int) -> <exn,read<$2402>,div> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001, (@implicit/monoid?monoid: monoid<$2401>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$2401>) -> <exn,read<$2402>,div> (($2401, $2401) -> $2401))(plpl: $2401, (!std/core/types/ref/(!): (ref : ref<$2402,vector<$2401>>, @implicit/hdiv : hdiv<$2402,vector<$2401>,<exn,div>>) -> <read<$2402>,exn,div> vector<$2401>
?hdiv=iev@2533segseg: segtree<$2402,$2401>.prodck/segtree/segtree/prod: (segtree : segtree<$2402,$2401>) -> <read<$2402>,exn,div> ref<$2402,vector<$2401>>)[ll: int]))std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)
        else
          (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)ll: int, plpl: $2401)std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)
      val (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)r'r': int, pr'pr': $2401)std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b) =
        if rr: int %std/core/int/(%): (int, int) -> <exn,read<$2402>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 >std/core/int/(>): (x : int, y : int) -> <exn,read<$2402>,div> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000 then
          (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)rr: int -std/core/int/(-): (x : int, y : int) -> <exn,read<$2402>,div> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001, (@implicit/monoid?monoid: monoid<$2401>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$2401>) -> <exn,read<$2402>,div> (($2401, $2401) -> $2401))((!std/core/types/ref/(!): (ref : ref<$2402,vector<$2401>>, @implicit/hdiv : hdiv<$2402,vector<$2401>,<exn,div>>) -> <read<$2402>,exn,div> vector<$2401>
?hdiv=iev@2673segseg: segtree<$2402,$2401>.prodck/segtree/segtree/prod: (segtree : segtree<$2402,$2401>) -> <read<$2402>,exn,div> ref<$2402,vector<$2401>>)[rr: int -std/core/int/(-): (x : int, y : int) -> <read<$2402>,exn,div> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001], prpr: $2401))std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)
        else
          (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)rr: int, prpr: $2401)std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)
      looploop: (l : int, r : int, pl : $2401, pr : $2401) -> <exn,read<$2402>,div> $2401(l'l': int /std/core/int/(/): (x : int, y : int) -> <exn,read<$2402>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010, r'r': int /std/core/int/(/): (x : int, y : int) -> <exn,read<$2402>,div> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010, pl'pl': $2401, pr'pr': $2401)
    else
      (@implicit/monoid?monoid: monoid<$2401>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$2401>) -> <exn,read<$2402>,div> (($2401, $2401) -> $2401))(plpl: $2401, prpr: $2401)
  looploop: (l : int, r : int, pl : $2401, pr : $2401) -> <div,exn,read<$2402>> $2401(
    leftleft: int +std/core/int/(+): (x : int, y : int) -> <div,exn,read<$2402>> int segseg: segtree<$2402,$2401>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$2402,$2401>) -> <div,exn,read<$2402>> int,
    rightright: int +std/core/int/(+): (x : int, y : int) -> <div,exn,read<$2402>> int segseg: segtree<$2402,$2401>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$2402,$2401>) -> <div,exn,read<$2402>> int,
    @implicit/monoid?monoid: monoid<$2401>.oneck/algebra/monoid/monoid/one: (monoid : monoid<$2401>) -> <div,exn,read<$2402>> $2401,
    @implicit/monoid?monoid: monoid<$2401>.oneck/algebra/monoid/monoid/one: (monoid : monoid<$2401>) -> <div,exn,read<$2402>> $2401
  )

// Return the smallest integer `k` between `start` (inclusive) and `end` (exclusive)
// such that the product from the `start`-th element (inclusive) to the `k`-th
// element (inclusive) holds `p`. If no such `k` exists, return `end`.
// The first element is at position 0 (0-based).
// `p` must be increasing.
pub fun binsearchck/segtree/binsearch: forall<a,e,h> (seg : segtree<h,a>, start : int, end : int, p : forall<h1> (a) -> <pure,read<h1>|e> bool, @implicit/monoid : monoid<a>) -> <pure,read<h>|e> int(
  segseg: segtree<$2839,$2837>: segtreeck/segtree/segtree: (H, V) -> V<hh: H,aa: V>,
  startstart: int: intstd/core/types/int: V,
  endend: int: intstd/core/types/int: V,
  pp: forall<h> ($2837) -> <pure,read<h>|$2838> bool: forall<h1h1: H> aa: V -> <purestd/core/pure: E,readstd/core/types/read: H -> X<h1h1: H>|std/core/types/effect-extend: (X, E) -> Eee: E> boolstd/core/types/bool: V,
  @implicit/monoid?monoid: monoid<$2837>: monoidck/algebra/monoid/monoid: V -> V<aa: V>
)result: -> <pure,read<3837>|3836> int: <purestd/core/pure: E,readstd/core/types/read: H -> X<hh: H>|std/core/types/effect-extend: (X, E) -> Eee: E> intstd/core/types/int: V
  inline fun extendextend: (rs : list<int>, pl : $2837) -> <pure,read<$2839>|$2838> (int, $2837)(rsrs: list<int>: liststd/core/types/list: V -> V<intstd/core/types/int: V>, plpl: $2837)result: -> <div,exn,read<$2839>|$2838> (int, $2837)
    match rsrs: list<int>
      Nilstd/core/types/Nil: forall<a> list<a> -> (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)endend: int +std/core/int/(+): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int segseg: segtree<$2839,$2837>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$2839,$2837>) -> <div,exn,read<$2839>|$2838> int, plpl: $2837)std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)
      Consstd/core/types/Cons: forall<a> (head : a, tail : list<a>) -> list<a>(rr: int, rs'rs': list<int>) ->
        val pl'pl': $2837 = (@implicit/monoid?monoid: monoid<$2837>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$2837>) -> <exn,read<$2839>,div|$2838> (($2837, $2837) -> $2837))(plpl: $2837, (!std/core/types/ref/(!): (ref : ref<$2839,vector<$2837>>, @implicit/hdiv : hdiv<$2839,vector<$2837>,<exn,div|$2838>>) -> <read<$2839>,exn,div|$2838> vector<$2837>
?hdiv=iev@2913segseg: segtree<$2839,$2837>.prodck/segtree/segtree/prod: (segtree : segtree<$2839,$2837>) -> <read<$2839>,exn,div|$2838> ref<$2839,vector<$2837>>)[rr: int])
        if pp: ($2837) -> <pure,read<$2839>|$2838> bool(pl'pl': $2837) then (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)rr: int, plpl: $2837)std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b) else extendextend: (rs : list<int>, pl : $2837) -> <div,exn,read<$2839>|$2838> (int, $2837)(rs'rs': list<int>, pl'pl': $2837)
  inline fun big-stepbig-step: (l : int, r : int, rs : list<int>, pl : $2837) -> <pure,read<$2839>|$2838> (int, $2837)(ll: int: intstd/core/types/int: V, rr: int: intstd/core/types/int: V, rsrs: list<int>: liststd/core/types/list: V -> V<intstd/core/types/int: V>, plpl: $2837)result: -> <div,exn,read<$2839>|$2838> (int, $2837)
    if rr: int <=std/core/int/(<=): (x : int, y : int) -> <div,exn,read<$2839>|$2838> bool ll: int then returnreturn: (int, $2837) extendextend: (rs : list<int>, pl : $2837) -> <pure,read<$2839>|$2838> (int, $2837)(rsrs: list<int>, plpl: $2837)std/core/types/Unit: ()
    val l'l': int = (ll: int +std/core/int/(+): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) /std/core/int/(/): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010
    val r'r': int = rr: int /std/core/int/(/): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010
    val rs'rs': list<int> = if rr: int %std/core/int/(%): (int, int) -> <div,exn,read<$2839>|$2838> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 ==std/core/int/(==): (x : int, y : int) -> <div,exn,read<$2839>|$2838> bool 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001 then Consstd/core/types/Cons: forall<a> (head : a, tail : list<a>) -> list<a>(rr: int -std/core/int/(-): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001, rsrs: list<int>) else rsrs: list<int>
    val pl'pl': $2837 = if ll: int %std/core/int/(%): (int, int) -> <exn,read<$2839>,div|$2838> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 ==std/core/int/(==): (x : int, y : int) -> <exn,read<$2839>,div|$2838> bool 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001 then (@implicit/monoid?monoid: monoid<$2837>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$2837>) -> <exn,read<$2839>,div|$2838> (($2837, $2837) -> $2837))(plpl: $2837, (!std/core/types/ref/(!): (ref : ref<$2839,vector<$2837>>, @implicit/hdiv : hdiv<$2839,vector<$2837>,<exn,div|$2838>>) -> <read<$2839>,exn,div|$2838> vector<$2837>
?hdiv=iev@3340segseg: segtree<$2839,$2837>.prodck/segtree/segtree/prod: (segtree : segtree<$2839,$2837>) -> <read<$2839>,exn,div|$2838> ref<$2839,vector<$2837>>)[ll: int]) else plpl: $2837
    if ll: int %std/core/int/(%): (int, int) -> <div,exn,read<$2839>|$2838> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 ==std/core/int/(==): (x : int, y : int) -> <div,exn,read<$2839>|$2838> bool 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001 &&std/core/types/(&&): (x : bool, y : bool) -> <div,exn,read<$2839>|$2838> bool pp: ($2837) -> <pure,read<$2839>|$2838> bool(pl'pl': $2837) then returnreturn: (int, $2837) (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)ll: int, plpl: $2837)std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)
    big-stepbig-step: (l : int, r : int, rs : list<int>, pl : $2837) -> <div,exn,read<$2839>|$2838> (int, $2837)(l'l': int.pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> <div,exn,read<$2839>|$2838> int, r'r': int, rs'rs': list<int>, pl'pl': $2837)
  inline fun small-stepsmall-step: (i : int, pl : $2837) -> <pure,read<$2839>|$2838> int(ii: int: intstd/core/types/int: V, plpl: $2837)result: -> <div,exn,read<$2839>|$2838> int
    if ii: int >=std/core/int/(>=): (x : int, y : int) -> <div,exn,read<$2839>|$2838> bool segseg: segtree<$2839,$2837>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$2839,$2837>) -> <div,exn,read<$2839>|$2838> int then
      ii: int
    else
      val pl'pl': $2837 = (@implicit/monoid?monoid: monoid<$2837>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$2837>) -> <exn,read<$2839>,div|$2838> (($2837, $2837) -> $2837))(plpl: $2837, (!std/core/types/ref/(!): (ref : ref<$2839,vector<$2837>>, @implicit/hdiv : hdiv<$2839,vector<$2837>,<exn,div|$2838>>) -> <read<$2839>,exn,div|$2838> vector<$2837>
?hdiv=iev@3624segseg: segtree<$2839,$2837>.prodck/segtree/segtree/prod: (segtree : segtree<$2839,$2837>) -> <read<$2839>,exn,div|$2838> ref<$2839,vector<$2837>>)[ii: int *std/core/int/(*): (int, int) -> <read<$2839>,exn,div|$2838> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010])
      if pp: ($2837) -> <pure,read<$2839>|$2838> bool(pl'pl': $2837) then
        small-stepsmall-step: (i : int, pl : $2837) -> <div,exn,read<$2839>|$2838> int(ii: int *std/core/int/(*): (int, int) -> <div,exn,read<$2839>|$2838> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010, plpl: $2837)
      else
        small-stepsmall-step: (i : int, pl : $2837) -> <div,exn,read<$2839>|$2838> int(ii: int *std/core/int/(*): (int, int) -> <div,exn,read<$2839>|$2838> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010 +std/core/int/(+): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001, pl'pl': $2837)
  val (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)bibi: int, plpl: $2837)std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b) = big-stepbig-step: (l : int, r : int, rs : list<int>, pl : $2837) -> <pure,read<$2839>|$2838> (int, $2837)(startstart: int +std/core/int/(+): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int segseg: segtree<$2839,$2837>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$2839,$2837>) -> <div,exn,read<$2839>|$2838> int, endend: int +std/core/int/(+): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int segseg: segtree<$2839,$2837>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$2839,$2837>) -> <div,exn,read<$2839>|$2838> int, [std/core/types/Nil: forall<a> list<a>]std/core/types/Nil: forall<a> list<a>, @implicit/monoid?monoid: monoid<$2837>.oneck/algebra/monoid/monoid/one: (monoid : monoid<$2837>) -> <div,exn,read<$2839>|$2838> $2837)
  val sisi: int = if bibi: int <std/core/int/(<): (x : int, y : int) -> <div,exn,read<$2839>|$2838> bool endend: int +std/core/int/(+): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int segseg: segtree<$2839,$2837>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$2839,$2837>) -> <div,exn,read<$2839>|$2838> int then small-stepsmall-step: (i : int, pl : $2837) -> <pure,read<$2839>|$2838> int(bibi: int, plpl: $2837) else bibi: int
  sisi: int -std/core/int/(-): (x : int, y : int) -> <div,exn,read<$2839>|$2838> int segseg: segtree<$2839,$2837>.leaf-countck/segtree/segtree/leaf-count: (segtree : segtree<$2839,$2837>) -> <div,exn,read<$2839>|$2838> int