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.