Segment Tree를 활용한 2D Range Update/Query
이 포스트는 Nabil Ibtehaz, Mohammad Kaykobad, Mohammad Sohel Rahman의 Multidimensional segment trees can do range queries and updates in logarithmic time 논문에서 핵심 아이디어를 가져와 작성한 것입니다. 독자가 1/2차원 세그먼트 트리와 Lazy propagation에 대한 지식을 알고 있다고 가정하고 글을 작성합니다. 아래에 제시된 코드는 모두 Kotlin으로 작성하였습니다. 목표 이 글의 목표는 2차원 세그먼트 트리를 이용해 $n \times m$ 크기의 2차원 배열 $A$에 다음과 같은 연산을 $O(\log n \log m)$ 시간에 수행하는 것입니다. Update: 모든 $(x, y)...