# Lazy segment tree

Maintain a numerical table `tab`

that implements the following operations in logarithmic time: for a range of table indices, query the maximum value, query the minimum value, query the sum, set all entries of that range to some value, add some value to all entries of that range.

## Segment tree

The data structure is an enhanced version of the segment tree, which is explained here.

Suppose that we have a segment tree for a table `tab`

of size 8 containing initially only zeros. Notice the usage of the half open interval, which might make some notations easier.
Suppose that we want to set `tab[i]`

to the value 7 for all i in the range [2,8). In a classical segment tree we would update all the leafs correspond to the entries `tab[2]`

to `tab[7]`

, here depicted in yellow.

The idea is to make lazy updates of the table `tab`

by storing in some nodes the instruction that the table value over the corresponding index range is to be set to 7. This will permit to reduce the time complexity of an update from linear to logarithmic time. To this purpose we attach with each node of the segment tree a value called `lazyset`

which, if not `None`

, represents this update instruction.
The following picture illustrates this example, depicting in yellow the nodes concerned by the update.
The values `maxval,minval,sumval`

of a node k represent the result of querying the maximum, the minimum or the sum over the entries in the table corresponding to the index range of k.

Now we have to implement a clearing procedure `clear`

which propagates this instruction to the immediate descendants. The query methods `max,min`

and `sum`

called on some node have to clear that node first.
For example when querying the minimum over the range [4,6), we have to clear all the nodes from the root of the tree up the node corresponding to the range [4,6), which is depicted in blue.

Similarly we can augment nodes with the instruction of *adding* a given value to the table over the corresponding index range. We call this value `lazyadd`

.

The update methods `set`

and `add`

as well as the query methods `max,min`

or `sum`

have logarithmic time complexity in the table size. The proof is similar as for the standard segment tree.