Lazy segment tree.

(Internal) 1-based indices

Use 1-based indices for 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

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

Invariant

• New operators always come from the left: \((\mathcal{newOp} <> \mathcal{oldOp}) \mathcal{acc}\) or \(\mathcal{newOp} `\mathcal{sact}` (\mathcal{oldOp} `\mathcal{sact}` \mathcal{acc})\).

• Folding is performed from the left to the right. Use Dual monoid if you need to reverse the folding direction.

Internals

See also: https://maspypy.com/segment-tree-%E3%81%AE%E3%81%8A%E5%8B%89%E5%BC%B72

Bottom-up folding

Bottom-up folding often needs less traversal than a top-down folding.

[-----------------------------]   [-]: vertices
[-------------] [-------------]   [*]: folded vertices ("glitch segments")
[-----] [*****] [*****] [-----]
[-] [*] [-] [-] [-] [-] [-] [-]
    ---------------- folding interval

Lazily propagated values for children

Each vertex has lazily propagated values. These values are stored for children and the value for the vertex is applied instantly. This lets the parent evaluation be done without checking the child's propagated value.

Propagation pruning

Propagations are only performed over the parent vertices of folded vertives:

[+++++++++++++++++++++++++++++]   [-]: vertices
[+++++++++++++] [+++++++++++++]   [*]: folded vertices ("glitch segments")
[-----] [*****] [*****] [-----]   [+]: propagated vertices (above the "glitch segments")
[-] [*] [-] [-] [-] [-] [-] [-]
    ---------------- folding interval

Note that the propagted vertices are pruned to be above the glitch segments only.

\(O(N)\) Creates a LazySegmentTree with mempty as the initial accumulated values.

\(O(N)\)

\(O(N)\) Creates LazySegmentTree with initial leaf values.

\(O(N)\)

\(O(N)\). TODO: Share the internal implementation with genearteLSTree takeing filling function.

\(O(\log N)\)

\(O(\log N)\)

\(O(\log N)\) Read one leaf. TODO: Faster implementation.

\(O(\log N)\)

\(O(\log N)\) Applies a lazy operator monoid over an interval, propagated lazily.

\(O(\log N)\) Acts on one leaf. TODO: Specialize the implementation.

\(O(\log N)\) Propagates the lazy operator monoids from the root to just before the glitch segments.

• iLeaf: Given with zero-based index.

Pruning

The propagation is performed from the root to just before the folded vertices. In other words, propagation is performed just before performing the first glitch. That's enough for both folding and acting.

\(O(1)\) Acts on a node.

Evaluation strategy

• The propagated value for the children are stored and propagated lazily.
• The propagated value to the vertex is evaluated instantly.

Invariants

• The new coming operator operator always comes from the left.

Propagates the operator onto the children. Push.

\(O(\log^2 N)\) The l, r indices are the zero-based leaf indices.

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

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