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

DOI10.1016/j.tcs.2020.11.034zbMath1477.68083arXiv1811.01226OpenAlexW3106889243MaRDI QIDQ2220857

Nabil Ibtehaz, M. Sohel Rahman, Mohammad Kaykobad

Publication date: 25 January 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.01226

zbMATH Keywords

multidimensional datasegment treetree data structuresdynamic range querylazy propagationrange sum query

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

Related Items (1)

Range updates and range sum queries on multidimensional points with monoid weights

Uses Software

• Python

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
• Fast Algorithms for Finding Nearest Common Ancestors
• Conjunctive, Subset, and Range Queries on Encrypted Data
• New Data Structures for Orthogonal Range Queries
• A Lower Bound on the Complexity of Orthogonal Range Queries
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• An efficient color representation for image retrieval

This page was built for publication: Multidimensional segment trees can do range updates in poly-logarithmic time