A SegmentTree is a list like data structure that can quickly apply associative operations over ranges. Most common associative operations: min, max, add, multiply, gcd, add over a ring.

This is also associative:

proc countThrees(a: int,b: int): int =
    result = 0
    if a == 3: result += 1
    if b == 3: result += 1

More information here: https://cp-algorithms.com/data_structures/segment_tree.html

If n is the number of elements inside the RQ, the RQ supports the following operations:

Memory used: O(n), about 4 * n to be precise
Changing a value at a specific index: O(log(n))
Setting a range to a value: O(log(n))
Computing an associative operation over a range: O(log(n))

It's however not possible to add elements to a SegmentTree after it's created. You need to create a new bigger SegmentTree and copy the data.

Inserting an element: O(n)
Deleting an element: O(n)

Examples:

var nbrs: seq[int] = @[]
for i in 1 .. 20:
  nbrs.add(i)
proc add(a, b: int): int =
  a + b

var st = toSegmentTree[int](nbrs, add)
echo st.query(3, 5)

Types

SegmentTree[T] = object data: seq[T] size: int assoc_operation: (T, T) -> T

Procs

proc toSegmentTree[T](arr: seq[T]; operator: proc (a, b: T): T): SegmentTree[T]

Create a range query from a sequence. The elements inside the seq are copied. Takes O(n) time where n = arr.len

proc `$`[T](rq: SegmentTree[T]): string

Convert the segment tree to a string, mainly for debug purposes.

Examples:

echo toSegmentTree(@[1, 2, 3], proc (a, b: int): int =
  max(a, b))

proc `[]=`[T](rq: var SegmentTree[T]; idx: int; val: T)

Edit an element at a specific index (in O(log(n)) time)

Examples:

var t = toSegmentTree(@[1, 2, 3], proc (a, b: int): int =
  max(a, b))
t[1] = 5

proc len[T](rq: SegmentTree[T]): int

Return the number of elements in the Segment Tree

proc `[]`[T](rq: SegmentTree[T]; idx: int): T

Access an element at a specific index (in O(log(n)) time)

proc query[T](rq: SegmentTree[T]; start, endp: int): T

Apply the operation of the segment tree over the range [start..endp] in O(log(n)) time

Examples:

var t = toSegmentTree(@[1, 2, 3], proc (a, b: int): int =
  a + b)
echo t.query(0, 2)

proc queryIdx[T](rq: SegmentTree[T]; start, endp: int): int

Get the index of the most "operatory" element of segment tree in the range [start..endp] in O(log(n)) time This only works when operator is a function that returns one of the operands like the "max" or "min" functions !

Examples:

var nbrs: seq[int] = @[]
for i in 1 .. 20:
  nbrs.add(1)
proc maxproc(a, b: int): int =
  max(a, b)

var st = toSegmentTree[int](nbrs, maxproc)
st[7] = 4
st[11] = 5
assert st.queryIdx(5, 10) == 7
assert st.queryIdx(4, 12) == 11
proc sayZero(a, b: int): int =
  if a == 0 or b == 0:
    return 0
  return a

var st2 = toSegmentTree[int](nbrs, sayZero)
st2[11] = 0
assert st2.queryIdx(0, 19) == 11

Iterators

iterator items[T](rq: SegmentTree[T]): T: Iterate over the segment tree in O(n) time.
iterator pairs[T](rq: SegmentTree[T]): (int, T): Iterate over the segment tree in O(n) time.

rangequeries

Types

Procs

Iterators