Version-Aware Lazy Segment Tree

The problem

Lazy propagation and persistence are each well understood on their own. Together they conflict.

Lazy propagation makes range updates fast by deferring them: an update writes a pending value at an internal node and pushes it down only when a later query forces the issue. Persistence, meanwhile, requires that every past version of the structure remain queryable, which means no node may ever be mutated in place — you copy the path you touch and leave the old nodes alone.

The conflict is that a lazy tag is a mutation scheduled for later. If you push a pending tag down while answering a query, you have just modified nodes that older versions still point at, and a historical range-sum query silently returns a value that was never true at that version. The failure is quiet: no crash, no assertion, just a wrong number. That is exactly the class of bug I find most interesting, and the reason this project exists.

Approach

I built the verification apparatus before the optimised structure, which is the opposite of the usual order and deliberate.

Two components are implemented. BruteForceArray is the historical correctness oracle: it takes a complete array copy per version, giving O(n) updates and O(n) worst-case queries. It is far too slow to be useful and that is fine — its only job is to be obviously right, so it can be differentially tested against something clever. LazySegmentTree is the non-persistent performance baseline at O(log n) for both update and query. Both support zero-based, inclusive range-add and range-sum over long long.

With an oracle and a baseline in place, the interesting structure has something to be judged against. Any candidate persistent implementation has to agree with the brute-force array on every version, and stay near the baseline’s asymptotics.

The verification setup does more work than the algorithms so far. Tests are deterministic GoogleTest suites run through CMake presets, and CI covers four compiler/platform combinations — GCC and Clang on Linux, MSVC on Windows, and Apple Clang on macOS — because undefined behaviour in a tree of raw pointers is exactly the kind of bug that passes on one toolchain and fails on another. The Linux Clang job additionally runs under AddressSanitizer and UndefinedBehaviorSanitizer, ClangFormat 18 is enforced, and every job uploads verbose logs and JUnit XML so a failure can be read rather than reproduced from scratch.

Where it stands

The correctness and performance baselines are implemented and verified. The partially persistent lazy segment tree itself is the next development phase and is not yet part of the public API — I would rather say that plainly than imply a finished result.

The honest limitations: an oracle proves agreement on the cases you generate, not correctness in general, and my generators encode my own assumptions about which version/update interleavings are dangerous. Sanitizers catch memory and UB faults that execute; they say nothing about paths the tests never reach. And the asymptotics I care about — O(log n) amortised updates with O(log n) historical queries and O(log n) new nodes per update — are the target, not yet a measured result.