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

Nabil Ibtehaz, M. Kaykobad, M. Sohel Rahman

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…