---
title: "algorithm-persistent-segment-tree — Mova code model"
description: "Mova code model of algorithms/src/persistent_segment_tree/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/persistent_segment_tree/mod.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/persistent_segment_tree/mod.rs.groupant/>

# algorithm-persistent-segment-tree

The groupant beside algorithms/src/persistent_segment_tree/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

## Facts

- **kind:** groupant
- **status:** partial
- **source:** [`algorithms/src/persistent_segment_tree/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/persistent_segment_tree/mod.rs)
- **source SHA-256:** `5f2af47008444ec0…`
- **repository folder:** [`algorithms/src/persistent_segment_tree/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/persistent_segment_tree/mod.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

## Components

| component | label | where |
|---|---|---|
| **approximant** | partial | [forward](#forward) |
| **ast** | partial | `syntax.json` |
| **cost** | partial | [cost](#cost) |
| **descriptant** | partial | [descriptant](#descriptant) |
| **invariant** | partial | [invariant](#invariant) |
| **tests** | partial | [tests](#tests) |

## Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

| id | type | label | where |
|---|---|---|---|
| `algorithm-persistent-segment-tree-behavior-complement` | behavior_complement | partial source model | [behavior-complement](#behavior-complement) |
| `algorithm-persistent-segment-tree-reverse-reconstruction` | reverse_reconstruction | partial source model | [reverse-reconstruction](#reverse-reconstruction) |
| `algorithm-persistent-segment-tree-history-frame` | persistent_frame | partial source model | [history-frame](#history-frame) |
| `algorithm-persistent-segment-tree-transactional-publication` | rollback_atomicity | partial source model | [transactional-publication](#transactional-publication) |
| `algorithm-persistent-segment-tree-wide-arithmetic` | signed_sum_embedding | partial source model | [wide-arithmetic](#wide-arithmetic) |
| `algorithm-persistent-segment-tree-path-budget` | structural_allocation_bound | partial source model | [path-budget](#path-budget) |

## Model text


### model

## Persistent point replacement and range sums
2026-10-30. Original implementation. Origin: Driscoll et al.,
"Making Data Structures Persistent" (1989). Prospective model retained.

### domain
Finite i64 snapshots, usize version IDs and indices, half-open ranges.
Sums and checked additions use i128. On targets with usize width <=64 every
mathematical sum of a realizable i64 slice fits i128. Version zero exists
even for empty input. No configured memory cap; allocation failure is outside
Result. Public errors distinguish version, index, range and overflow.

### forward
Build a balanced binary interval tree, splitting at floor(length/2).
Leaves store i64 widened to i128; internal nodes sum children. Arena appends
nodes and roots retain historical root IDs. set validates version, then index,
records arena length and recursively copies the chosen path. Successful
replacement publishes one new root; a returned error truncates appended
nodes before returning. range_sum validates version then endpoints, returns
zero for empty intervals, and recursively sums fully covered nodes using
checked i128 addition.

### invariant
All nodes reachable from a published root are immutable. Leaves correspond
to original positions; node sums equal the represented interval sum.
Every root denotes one complete snapshot; branches may share nodes.
Only newly allocated nodes may be truncated on failure. No root is published
until replacement finishes. Midpoints start+(end-start)/2 avoid overflow.
Queries stop before child access at disjoint or fully covered leaves.

### cost
For n>0, initial nodes exactly 2n-1. Successful update appends at most
ceil(log2(n))+1 nodes and one root, even if replacement equals old value.
Build O(n), query and replacement O(log(n+1)), stack O(log(n+1)).
After u updates storage O(n+u log(n+1)), plus u+1 root Options.
For n=1,000,000, initial payload is (1,999,999)*size_of(Node), plus roots;
each update appends at most 21 nodes. Node layout is target dependent.
No reclamation or compaction; historical versions remain reachable. Clone
copies the arena and roots. Allocation exhaustion is not caught or promised
atomic by the Result contract. Queries allocate nothing.

### behavior-complement
Type behavior_complement. Universe is valid snapshot histories, requested
operations and candidate returned states/results. R is the forward relation.
Excluded behaviors include mutation of any historical root/node, publication
of a partial update, invalid-range success, ignored invalid versions even on
empty ranges, wrapped sums, and partial arena extension after a returned
error. Allocation abort/panic is outside this relation.

### reverse-reconstruction
Type reverse_reconstruction. A fixed-version range sum s admits all i64
arrays whose selected entries sum to s; outside entries are free. A complete
set of singleton observations uniquely determines that version's array but
does not recover update ancestry, allocation IDs or repeated equal writes.
New version v and replacement (i,x) leave the prior value at i ambiguous.
Failed calls preserve known prior state but do not identify the rejected
parameters from the Error category alone.

### history-frame
Type persistent_frame. Root v refers only to immutable nodes existing when
it was published. New path nodes reuse untouched child IDs; no operation
rewrites old nodes. Tests compare the entire previous arena prefix after
each branching update and query all previous Vec snapshots.

### transactional-publication
Type rollback_atomicity. Before recursive replacement remember m=nodes.len.
If any checked add fails, truncate back to m and do not append a root.
Version/index validation fails before any append. Exact node and root equality
is asserted after invalid calls and a deliberately injected internal overflow.
The injected state is outside the public invariant; it exercises a defensive
branch that realizable <=64-bit public inputs cannot reach.

### wide-arithmetic
Type signed_sum_embedding. Widen i64 before addition. Cancellation patterns
such as [MAX,MAX,MIN,MIN,1] retain exact subrange sums beyond i64 and total -1.
i128 checked addition prevents silent wrapping if platform/domain assumptions
change. No decomposition-dependent i64 overflow is exposed.

### path-budget
Type structural_allocation_bound. The floor-half split yields maximum depth
ceil(log2 n). One node per visited level means at most depth+1 appended nodes;
other branches are shared. Tests inspect node_count deltas for n=1..17,
including non-powers of two and repeated updates from older roots.

### tests
Five tests: branching Vec snapshots n=1..17 with 24 updates each; all historical
versions/all intervals checked after every update; invalid-call exact state,
wide cancellation/empty version, replacement mutation witness, and defensive
overflow rollback. Repeated profiles and controls are recorded in evidence.md.

### descriptant
Composition scope: build establishes node sums; replace preserves interval
shape and historical immutability; set is the publication/rollback boundary;
query relies on both invariants. Branching versions detect accidental latest-
root use that a linear update trace misses. Partial syntax omits semantics
and macro expansion. No numerical surrogate is offered: signed cancellation
makes relative error unstable and version identity remains exact. Certified
approximate replacement and composition guarantees are explicit gaps.

### evidence

#### Evidence, 2026-10-30

5 tests pass twice debug and twice release. Normalized named outcomes match within each profile. Compiled control replacement_control: replacement leaf value incremented by one fails by named assertion (exit 101), then source is restored byte-for-byte and all focused tests pass. Syntax projections run twice and compare byte-for-byte.

External logs: $MOVA_DATA/runs/octopus-wave18-structures-2026-10-30/. Finite tests provide no universal proof or timing guarantee.

Source algorithms/src/persistent_segment_tree/mod.rs: sha256 5f2af47008444ec0307365c7d0d189a3382510112a5bdfb4f65760984dc16f3b

- persistent_segment_tree-debug-1.log: sha256 17bc81ad86efc73497bb9408b21afdf2cd42b8413ae9e661efbc35e5cc0a02c5
- persistent_segment_tree-debug-2.log: sha256 41fa8b446fe847a65dae9b03eae10396e8f2444b46ae673e6fe2caaedcd43063
- persistent_segment_tree-release-1.log: sha256 29bc9d8f14663c5a85a0b56708d920494dabc618d879c33dd0039b278bdc3c13
- persistent_segment_tree-release-2.log: sha256 e2de0a8a92e7e1bcc389e4d67ee19ee974b4507bbf67d03453aa80195925f9d0
- persistent_segment_tree-mutant.log: sha256 45034d1881c87296bbc863b173cfa9c9cc944702199d1794324462e71c7b7488
- persistent_segment_tree-restored.log: sha256 10faf1f126daeeb9b952938663ec0fe546c3a7ca1cad658ac0b71b92f5662cbc
- syntax.json: sha256 d6e291c3fa311e03d9b498efb55ee35ddd142a21997c78263f3bde443acfc5c5

### prospective

#### Prospective model, 2026-10-30
Finite i64 snapshots; versioned half-open sums with checked i128 node arithmetic. Initial binary interval tree, then copy only root-to-leaf path on replacement. Historical nodes and roots immutable. Returned update errors truncate appended nodes exactly. Query sums use i128. Empty input has one empty version. Initial 2n-1 nodes; at most ceil(log2 n)+1 appended nodes per update and one root; O(log n) updates/queries, O(n+u log n) storage. No configured cap; allocation failures outside Result. Complement excludes stale-version mutation, wrapped sums, partial errors. A sum s leaves all arrays totaling s compatible; all singleton observations reconstruct a snapshot but not update history. Signed cancellation precludes a useful relative-error surrogate here.