// Fenwick tree
module fenwick

import int64

abstract struct fenwickck/fenwick/fenwick: H -> V<hh: H>
  treetree: ref<6,vector<int>>: refstd/core/types/ref: (H, V) -> V<hh: H,vectorstd/core/types/vector: V -> V<intstd/core/types/int: V>>

// Create a Fenwick tree
pub fun fenwickck/fenwick/fenwick: forall<h> (size : int) -> (alloc<h>) fenwick<h>(sizesize: int: intstd/core/types/int: V): allocstd/core/types/alloc: H -> X<hh: H> fenwickck/fenwick/fenwick: H -> V<hh: H>
  Fenwickck/fenwick/Fenwick: forall<h> (tree : ref<h,vector<int>>) -> fenwick<h>(refstd/core/types/ref: forall<a,h> (value : a) -> (alloc<h>) ref<h,a>(vectorstd/core/vector.2: forall<a> (n : int, default : a) -> vector<a>(sizesize: int +std/core/(+).4: (x : int, y : int) -> int 1, 0)))

pub fun sizeck/fenwick/size: forall<h> (f : fenwick<h>) -> (read<h>) int(ff: fenwick<$167>: fenwickck/fenwick/fenwick: H -> V<hh: H>): readstd/core/types/read: H -> X<hh: H> intstd/core/types/int: V
  (!std/core/types/(!): forall<h,a,e> (ref : ref<h,a>) -> <read<h>|e> a with hdiv<h,a,e>ff: fenwick<$167>.treeck/fenwick/tree: forall<h> (fenwick : fenwick<h>) -> ref<h,vector<int>>).lengthstd/core/length.2: forall<a> (v : vector<a>) -> int -std/core/(-).4: (x : int, y : int) -> int 1

// 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)
  (xx: int.int64std/core/int64: (i : int) -> int64.andstd/num/int64/and: (int64, int64) -> int64(xx: int.negatestd/core/negate: (i : int) -> int.int64std/core/int64: (i : int) -> int64)).intstd/core/int.5: (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<h> (f : fenwick<h>, index : int, value : int) -> <exn,read<h>,write<h>> ()(ff: fenwick<$375>: fenwickck/fenwick/fenwick: H -> V<hh: H>, indexindex: int: intstd/core/types/int: V, valuevalue: int: intstd/core/types/int: V): <std/core/types/(<>): Eexnstd/core/exn: HX,readstd/core/types/read: H -> X<hh: H>,writestd/core/types/write: H -> X<hh: H>> (std/core/types/(): V)std/core/types/(): V
  val ss: int = ff: fenwick<$375>.sizeck/fenwick/size: forall<h> (f : fenwick<h>) -> (read<h>) int
  if indexindex: int <=std/core/(<=).1: (x : int, y : int) -> bool 0 ||std/core/types/(||): (x : bool, y : bool) -> bool indexindex: int >std/core/(>).1: (x : int, y : int) -> bool ss: int then "out of bounds".throwstd/core/throw: forall<a> (message : string, info : ?exception-info) -> exn a
  ff: fenwick<$375>.treeck/fenwick/tree: forall<h> (fenwick : fenwick<h>) -> ref<h,vector<int>>.modifystd/core/types/modify: forall<h,a,b,e> (ref : ref<h,a>, f : forall<h1> (local-var<h1,a>) -> <local<h1>|e> b) -> <read<h>,write<h>|e> b with hdiv<h,a,e> fn(tt: local-var<$456,vector<int>>)
    // body, body2 をインライン展開すると segmentation fault が発生する (?)
    // また、local<_> を _ に変えると型推論が失敗する (?)
    fun bodybody: () -> (local<$456>) ()(): localstd/core/types/local: H -> X<__w-l31-c23: H> (std/core/types/(): V)std/core/types/(): V
      varstd/core/hnd/local-var: forall<a,b,e,h> (init : a, action : (l : local-var<h,a>) -> <local<h>|e> b) -> <local<h>|e> b istd/core/types/local-scope: forall<a,e> (action : forall<h> () -> <local<h>|e> a) -> e a := indexindex: int
      unsafe-no-divstd/core/types/unsafe-no-div: forall<a,e> (action : () -> <div|e> a) -> e a{
        fun body2body2: () -> <div,local<$460>,local<$456>> ()(): __w-l34-c22: E (std/core/types/(): V)std/core/types/(): V
          // s の代わりに f.size を使うと型に read<_> が2回現れてしまう
          whilestd/core/while: forall<e> (predicate : () -> <div|e> bool, action : () -> <div|e> ()) -> <div|e> () { ii: int <=std/core/(<=).1: (x : int, y : int) -> bool ss: int }
            val i'i': int = ii: int
            // mask<local> と unsafe-no-exn の順序は入れ替えてはいけない
            mask_1: H<localstd/core/types/local: H -> X>{ unsafe-no-exnstd/core/unsafe-no-exn: forall<a,e> (action : () -> <exn|e> a) -> e a{ tt: local-var<$456,vector<int>>[std/core/([]).1: forall<a,e,h> (self : local-var<h,vector<a>>, index : int, assigned : a) -> <local<h>,exn|e> ()i'i': int] := tt: vector<int>[std/core/([]): forall<a> (v : vector<a>, index : int) -> exn ai'i': int] +std/core/(+).4: (x : int, y : int) -> int valuevalue: int }}
            ii: local-var<$460,int> :=std/core/types/local-set: forall<a,e,h> (v : local-var<h,a>, assigned : a) -> <local<h>|e> () ii: int +std/core/(+).4: (x : int, y : int) -> int ii: int.rightmost-oneck/fenwick/rightmost-one: (x : int) -> int
        body2body2: () -> <div,local<$460>,local<$456>> ()()
      }
    bodybody: () -> (local<$456>) ()()

// 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<h> (f : fenwick<h>, end : int) -> <exn,read<h>> int(ff: fenwick<$866>: fenwickck/fenwick/fenwick: H -> V<hh: H>, endend: int: intstd/core/types/int: V): <std/core/types/(<>): Eexnstd/core/exn: HX,readstd/core/types/read: H -> X<hh: H>> intstd/core/types/int: V
  if endend: int <std/core/(<).1: (x : int, y : int) -> bool 0 ||std/core/types/(||): (x : bool, y : bool) -> bool endend: int >std/core/(>).1: (x : int, y : int) -> bool ff: fenwick<$866>.sizeck/fenwick/size: forall<h> (f : fenwick<h>) -> (read<h>) int then "out of bounds".throwstd/core/throw: forall<a> (message : string, info : ?exception-info) -> exn a
  varstd/core/hnd/local-var: forall<a,b,e,h> (init : a, action : (l : local-var<h,a>) -> <local<h>|e> b) -> <local<h>|e> b sumstd/core/types/local-scope: forall<a,e> (action : forall<h> () -> <local<h>|e> a) -> e a := 0
  varstd/core/hnd/local-var: forall<a,b,e,h> (init : a, action : (l : local-var<h,a>) -> <local<h>|e> b) -> <local<h>|e> b ii: local-var<$870,int> := endend: int
  unsafe-no-divstd/core/types/unsafe-no-div: forall<a,e> (action : () -> <div|e> a) -> e a {
    whilestd/core/while: forall<e> (predicate : () -> <div|e> bool, action : () -> <div|e> ()) -> <div|e> () { ii: int >std/core/(>).1: (x : int, y : int) -> bool 0 }
      sumsum: local-var<$870,int> :=std/core/types/local-set: forall<a,e,h> (v : local-var<h,a>, assigned : a) -> <local<h>|e> () sumsum: int +std/core/(+).4: (x : int, y : int) -> int (!std/core/types/(!): forall<h,a,e> (ref : ref<h,a>) -> <read<h>|e> a with hdiv<h,a,e>ff: fenwick<$866>.treeck/fenwick/tree: forall<h> (fenwick : fenwick<h>) -> ref<h,vector<int>>)[std/core/([]): forall<a> (v : vector<a>, index : int) -> exn aii: int]
      ii: local-var<$870,int> :=std/core/types/local-set: forall<a,e,h> (v : local-var<h,a>, assigned : a) -> <local<h>|e> () ii: int -std/core/(-).4: (x : int, y : int) -> int ii: int.rightmost-oneck/fenwick/rightmost-one: (x : int) -> int
  }
  sumsum: int