문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

이 문제는 기본적인 Segment Tree 개념을 기반으로, 2D Segment Tree를 구현해야 한다.

Algorithm

column을 기준으로 각 범위마다, row 기준 ST를 갖도록 만든다.
이후, update와 getSum을 column 기준으로 쪼개고, 해당 범위에서 다시 row 기준으로 쪼개도록 recursive 하게 해결한다.

Data Structure

• ST[][]: Two-dimensional Segment Tree.

결과

Other

시간 복잡도는, 매 query 마다 O(logN*logN)이다.

매개변수의 크기를 최소화 하여 시간 초과를 해결했다.
construct를 따로 두지 않고 update로만 초기화했더니, 시간이 많이 걸려 수정하였다.