// Fenwick tree
module ck/fenwickck/fenwick

import std/num/int64std/num/int64
import std/core/undivstd/core/undiv
import std/core/unsafestd/core/unsafe
import ck/algebra/monoidck/algebra/monoid

abstract struct fenwickck/fenwick/fenwick: (H, V) -> V<hh: H,aa: V>
  treeck/fenwick/fenwick/tree: forall<h,a> (fenwick : fenwick<h,a>) -> ref<h,vector<a>>: refstd/core/types/ref: (H, V) -> V<hh: H,vectorstd/core/types/vector: V -> V<aa: V>>

// Create a Fenwick tree
pub fun fenwickck/fenwick/fenwick: forall<a,h> (size : int, @implicit/monoid : monoid<a>) -> (alloc<h>) fenwick<h,a>(sizesize: int: intstd/core/types/int: V, @implicit/monoid?monoid: monoid<$145>: monoidck/algebra/monoid/monoid: V -> V<aa: V>)result: -> (alloc<214>) fenwick<214,213>: allocstd/core/types/alloc: H -> X<hh: H> fenwickck/fenwick/fenwick: (H, V) -> V<hh: H,aa: V>
  Fenwickck/fenwick/Fenwick: forall<h,a> (tree : ref<h,vector<a>>) -> fenwick<h,a>(refstd/core/types/ref: (value : vector<$145>) -> (alloc<$146>) ref<$146,vector<$145>>(vectorstd/core/vector/vector: (n : int, default : $145) -> (alloc<$146>) vector<$145>(sizesize: int +std/core/int/(+): (x : int, y : int) -> (alloc<$146>) int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001, monoid?monoid: monoid<$145>.oneck/algebra/monoid/monoid/one: (monoid : monoid<$145>) -> (alloc<$146>) $145)))

pub inline fun sizeck/fenwick/size: forall<a,h> (f : fenwick<h,a>) -> <div,read<h>> int(ff: fenwick<$223,$222>: fenwickck/fenwick/fenwick: (H, V) -> V<hh: H,aa: V>)result: -> <div,read<281>> int: <std/core/types/total: Edivstd/core/types/div: X,readstd/core/types/read: H -> X<hh: H>> intstd/core/types/int: V
  (!std/core/types/ref/(!): (ref : ref<$223,vector<$222>>, @implicit/hdiv : hdiv<$223,vector<$222>,div>) -> <read<$223>,div> vector<$222>
?hdiv=iev@248ff: fenwick<$223,$222>.treeck/fenwick/fenwick/tree: (fenwick : fenwick<$223,$222>) -> <read<$223>,div> ref<$223,vector<$222>>).lengthstd/core/vector/length: (v : vector<$222>) -> <read<$223>,div> int -std/core/int/(-): (x : int, y : int) -> <read<$223>,div> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001

// Find the rightmost 1 of the binary representation of `x`.
// Return 0 if `x` = 0.
// `x` must be within [-2^63, 2^63 - 1), the range of 64-bit signed integers.
fun rightmost-oneck/fenwick/rightmost-one: (x : int) -> int(xx: int: intstd/core/types/int: V)result: -> total int
  (xx: int.int64std/num/int64/int64: (i : int) -> int64.andstd/num/int64/and: (int64, int64) -> int64(xx: int.negatestd/core/int/negate: (i : int) -> int.int64std/num/int64/int64: (i : int) -> int64)).intstd/num/int64/int: (i : int64) -> int

// Add a value to an element.
// The first element is at position 1 (1-based).
// Raise an exception if `index` <= 0 or `index` > `f.size`.
pub fun addck/fenwick/add: forall<a,h> (f : fenwick<h,a>, index : int, value : a, @implicit/monoid : monoid<a>) -> <div,exn,read<h>,write<h>> ()(ff: fenwick<$316,$315>: fenwickck/fenwick/fenwick: (H, V) -> V<hh: H,aa: V>, indexindex: int: intstd/core/types/int: V, valuevalue: $315: aa: V, @implicit/monoid?monoid: monoid<$315>: monoidck/algebra/monoid/monoid: V -> V<aa: V>)result: -> <div,exn,read<572>,write<572>> (): <std/core/types/total: Edivstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V,readstd/core/types/read: H -> X<hh: H>,writestd/core/types/write: H -> X<hh: H>> (std/core/types/unit: V)std/core/types/unit: V
  val ss: int = ff: fenwick<$316,$315>.sizeck/fenwick/size: (f : fenwick<$316,$315>) -> <div,read<$316>,exn,write<$316>> int
  if indexindex: int <=std/core/int/(<=): (x : int, y : int) -> <exn,read<$316>,write<$316>,div> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000 ||std/core/types/(||): (x : bool, y : bool) -> <exn,read<$316>,write<$316>,div> bool indexindex: int >std/core/int/(>): (x : int, y : int) -> <exn,read<$316>,write<$316>,div> bool ss: int then "out of bounds"literal: string
count= 13.throwstd/core/exn/throw: (message : string, info : ? exception-info) -> <exn,read<$316>,write<$316>,div> ()
  ff: fenwick<$316,$315>.treeck/fenwick/fenwick/tree: (fenwick : fenwick<$316,$315>) -> <exn,read<$316>,write<$316>,div> ref<$316,vector<$315>>.modifystd/core/types/modify: (ref : ref<$316,vector<$315>>, f : forall<h> (local-var<h,vector<$315>>) -> <local<h>,exn,div> (), @implicit/hdiv : hdiv<$316,vector<$315>,<exn,div>>) -> <read<$316>,write<$316>,exn,div> ()
?hdiv=iev@428 fnfn: forall<h> (t : local-var<h,vector<$315>>) -> <exn,local<h>,div> ()(tt: local-var<$451,vector<$315>>)
    fun looploop: (i : int) -> <exn,local<$451>> ()(ii: int)result: -> <exn,local<$451>> ()
      if ii: int <=std/core/int/(<=): (x : int, y : int) -> <exn,local<$451>> bool ss: int then
        tt: local-var<$451,vector<$315>>[ii: int] := (@implicit/monoid?monoid: monoid<$315>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$315>) -> <exn,local<$451>> (($315, $315) -> $315))(tt: vector<$315>
?hdiv=iev@505[ii: int], valuevalue: $315)
        looploop: (i : int) -> <exn,local<$451>> ()((ii: int +std/core/int/(+): (x : int, y : int) -> <exn,local<$451>> int ii: int.rightmost-oneck/fenwick/rightmost-one: (x : int) -> <exn,local<$451>> int).pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> <exn,local<$451>> int)std/core/types/Unit: ()
    looploop: (i : int) -> <exn,local<$451>,div> ()(indexindex: int)

// Return the sum from the first element to the `end`-th element (inclusive).
// The first element is at position 1 (1-based).
// For convenience, return 0 if `end` = 0.
// Raise an exception if `end` < 0 or `end` > `f.size`.
pub fun prefix-sumck/fenwick/prefix-sum: forall<a,h> (f : fenwick<h,a>, end : int, @implicit/monoid : monoid<a>) -> <div,exn,read<h>> a(ff: fenwick<$581,$580>: fenwickck/fenwick/fenwick: (H, V) -> V<hh: H,aa: V>, endend: int: intstd/core/types/int: V, @implicit/monoid?monoid: monoid<$580>: monoidck/algebra/monoid/monoid: V -> V<aa: V>)result: -> <div,exn,read<802>> 801: <std/core/types/total: Edivstd/core/types/div: X,exnstd/core/exn/exn: (E, V) -> V,readstd/core/types/read: H -> X<hh: H>> aa: V
  if endend: int <std/core/int/(<): (x : int, y : int) -> <div,read<$581>,exn> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000 ||std/core/types/(||): (x : bool, y : bool) -> <div,read<$581>,exn> bool endend: int >std/core/int/(>): (x : int, y : int) -> <div,read<$581>,exn> bool ff: fenwick<$581,$580>.sizeck/fenwick/size: (f : fenwick<$581,$580>) -> <div,read<$581>,exn> int then "out of bounds"literal: string
count= 13.throwstd/core/exn/throw: (message : string, info : ? exception-info) -> <exn,div,read<$581>> ()
  fun looploop: (i : int, sum : $580) -> <exn,read<$581>> $580(ii: int, sumsum: $580)result: -> <exn,read<$581>> $580
    if ii: int >std/core/int/(>): (x : int, y : int) -> <exn,read<$581>> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000 then
      looploop: (i : int, sum : $580) -> <exn,read<$581>> $580(
        (ii: int -std/core/int/(-): (x : int, y : int) -> <exn,read<$581>> int ii: int.rightmost-oneck/fenwick/rightmost-one: (x : int) -> <exn,read<$581>> int).pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> <exn,read<$581>> int,
        (@implicit/monoid?monoid: monoid<$580>.mulck/algebra/monoid/monoid/mul: (monoid : monoid<$580>) -> <exn,read<$581>> (($580, $580) -> $580))(sumsum: $580, (!std/core/types/ref/(!): (ref : ref<$581,vector<$580>>, @implicit/hdiv : hdiv<$581,vector<$580>,exn>) -> <read<$581>,exn> vector<$580>
?hdiv=iev@749ff: fenwick<$581,$580>.treeck/fenwick/fenwick/tree: (fenwick : fenwick<$581,$580>) -> <read<$581>,exn> ref<$581,vector<$580>>)[ii: int])
      )
    else
      sumsum: $580
  looploop: (i : int, sum : $580) -> <exn,read<$581>,div> $580(endend: int, @implicit/monoid?monoid: monoid<$580>.oneck/algebra/monoid/monoid/one: (monoid : monoid<$580>) -> <exn,read<$581>,div> $580)