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
import ck/algebra/monoidck/algebra/monoid
import ck/segtreeck/segtree

fun main()
  val seg = segtree(10, @implicit/monoid=int/add/monoidck/algebra/monoid/int/add/monoid: monoid<int>)

  seg.set(1, 3, @implicit/monoid=int/add/monoidck/algebra/monoid/int/add/monoid: monoid<int>)
  seg.set(3, 8, @implicit/monoid=int/add/monoidck/algebra/monoid/int/add/monoid: monoid<int>)
  seg.productck/segtree/product: forall<a,h> (seg : segtree<h,a>, left : int, right : int, @implicit/monoid : monoid<a>) -> <read<h>,div,exn> a(0, 10, @implicit/monoid=int/add/monoidck/algebra/monoid/int/add/monoid: monoid<int>).println // 11

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.

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