Segment tree

Usage:

import ck/segtree

// 1. Define a monoid
fun mon(): monoid<int>
  Monoid(0, (+))

fun main()
  // 2. Create a segment tree
  val t = segtree(10, mon())

  // 3. Manipulate it (see below)
  t.set(1, 3)
  t.set(3, 8)
  t.product(0, 10).println // 11
import ck/segtree

// 1. Define a monoid
fun monck/segtree/mon: forall<h,a> (segtree : segtree<h,a>) -> monoid<a>(): monoidck/segtree/monoid: V -> V<intstd/core/types/int: V>
  Monoidck/segtree/Monoid: forall<a> (one : a, mul : (a, a) -> a) -> monoid<a>(0, (+))

fun main()
  // 2. Create a segment tree
  val t = segtree(10, monck/segtree/mon: forall<h,a> (segtree : segtree<h,a>) -> monoid<a>())

  // 3. Manipulate it (see below)
  t.set(1, 3)
  t.set(3, 8)
  t.productck/segtree/product: forall<a,h> (seg : segtree<h,a>, left : int, right : int) -> <read<h>,div,exn> a(0, 10).println // 11

Get the k-th element. The first element is at position 0 (0-based).

Return the largest integer k such that the product from the first element (inclusive) to the k-th element (exclusive) holds p. The first element is at position 0 (0-based). p must be decreasing and the product of the empty interval must hold p.

Return the product from the left-th element (inclusive) to right-th element (exclusive). The first element is at position 0 (0-based).

Create a segment tree.

Set a value to an element. The first element is at position 0 (0-based).

Apply a function to an element. The first element is at position 0 (0-based).

ck/segtree▲toc

Segment tree

ck/segtree ▲toc