Segment Tree With Lazy Propagation

Applying a correction across a whole window of stored values - "shift every bar in this session's range by a spread adjustment", "apply a rolling correction across a range of stored ticks" - is an O(n) loop with a plain array: touch every index in the range, every time. That is fine for one adjustment, but a series that gets adjusted repeatedly over overlapping windows pays that O(n) cost again on every call, and the cost compounds with however many overlapping adjustments have already happened. A segment tree covers the array with O(log n) nodes at every level, so any query range decomposes into at most O(log n) of them. Lazy propagation is what keeps a RANGE UPDATE at that same O(log n): instead of pushing an update down to every leaf immediately, it is parked as a pending delta on the O(log n) nodes that exactly cover the requested range, and only pushed one level further down the next time a query or another update actually needs to look inside that subtree. A node with no reason to be visited again never pays the cost of the update at all until it is. UpdateRange(l, r, delta) adds delta to every element in [l, r]. QuerySum(l, r) reads the current range sum back. Both are checked in the demo against a brute-force parallel array that applies the same updates with a plain O(n) loop - if the tree and the brute-force answer ever disagreed, the lazy propagation logic would have a bug, so this is a genuine correctness check built into the demo, not just an illustration of the API. Notes and limitations - This tree supports range-ADD updates and range-SUM queries only. A range-ASSIGN (set every element in a range to a fixed value) or a range-MIN/MAX query would each need their own lazy value and combine rule - genuinely different structures, not a parameter switch on this one. Build a separate tree if that operation is needed. - l and r passed to UpdateRange()/QuerySum() are clamped to the tree's own [0, Size()-1] bounds rather than raising an error on an out-of-range index - convenient for a caller doing a rolling window near either end of the series, at the cost of silently ignoring a genuinely wrong index rather than flagging it. - Build() is O(n) and discards all prior pending updates - it is a full reset, not a way to extend an existing tree with new elements. There is no Resize(); build a new, larger tree and re-apply UpdateRange() calls if the underlying series grows. - Recursion depth is O(log n) - for any bar-count-scale n this is a handful of levels, well within MQL4's default stack.

Script · MT4 · v1.0 · Free

Tags: Trading Sessions · MT4 Script · MQL4 Source Code

MQL4 & MQL5 scripts · PolyMaria