A mutable segment tree backed by a complete binary tree.

Overview

A segment tree is a complete binary tree of monoid folding results. Each vertex corresponds to a folding range and the result.

Typical monoids

• Sum (+), Product (*)
• Max (max), Min (min)
• Any (||), All (&&)

(Internal) 1-based indices

Use 1-based indices for super handy vertex indices:

           1             |
     2           3       | height = 4 = log_2 16
  4     5     6     7    |
08 09 10 11 12 13 14 15  v
^
+-- nVerts / 2

0  1  2  3  4  5  6  7   -- iLeaf is given by user and uses zero-based indices.

- parent = v .>>. 1
- childL = v .<<. 1
- childR = v .<<. 1 .|. 1

Bottom-up vs top-down folding implementation

Most of the time, the top-down approach has to retrieve the values of the bottom leaves. So bottom-up implementation is almost always faster.

\(O(\log N)\) Creates a segment tree for n leaves.

\(\Theta(N)\) Creates a segment tree from the given leaf values.

\(O(\log N)\) Reads a leaf value.

\(O(\log N)\) (Internal) Updates parent nodes after modifying a leaf.

\(\Theta(\log N)\) Writes a leaf value.

\(\Theta(\log N)\) Writes a leaf value and returns the old value.

\(\Theta(\log N)\) Modifies a leaf value.

\(O(\log N)\) Folds a non-empty [l, r] span. Returns a broken avlue when given invalid range (so this is actually unsafeFoldSTree).

\(O(\log N)\) Folds a non-empty [l, r] span. Returns Nothing when given invalid range.

\(O(1)\) Reads the whole span segment.

\(O(\log^2 N)\)

Typical problems

• PAST 07 - L Find minimum value indices.

\(O(\log^2 N)\)

\(O(\log^2 N)\)

\(\Theta(N)\) Freezes the leaf values making a copy.

\(\Theta(1)\) Freezes the leaf values without making a copy.