Lazy Segment Tree
AlgorithmsHardApply logarithmic range additions and trace deferred tag propagation steps.
Alt+Shift+L
Configuration Panel
Segment Tree Node Segments
Double-click empty canvas to create root, select node to add child or delete.
Time Complexity
O(log N) lazy query & updates
Auxiliary Space Complexity
O(N) segment tree & lazy tag sizes
Conceptual Overview
A Lazy Segment Tree optimizes range update operations (e.g., adding a value to all array elements in a range [L, R]) to logarithmic time by deferring child updates until they are queried.
Algorithm Mechanism
Instead of updating all leaves, range updates store 'lazy tags' at high-level segment nodes. When queries or updates traverse down, these tags are pushed to children (tag propagation).
Source: CP-Algorithms reference guide