Multidimensional segment trees can do range updates in poly-logarithmic time

Updating and querying on a range is a classical algorithmic problem with a multitude of applications. The Segment Tree data structure is particularly notable in handling the range query and update operations. A Segment Tree divides the range into disjoint segments and merges them together to perform range queries and range updates elegantly. Although this data structure is remarkably potent for 1-dimensional problems, it falls short in higher dimensions. Lazy Propagation enables the operations to be computed in O ( l o g n ) time in a single dimension. However, the concept of lazy propagation could not be translated to higher-dimensional cases, which imposes a time complexity of O ( n k − 1 l o g n )…