이번 글에서는, 아래의 네 가지 조건으로 만들어지는 다양한 상황에서 알맞은 방식으로 구간 합을 구하는 테크닉을 소개하려고 합니다. 1차원 공간 vs 2차원 공간 점 업데이트 vs 구간 업데이트 점 쿼리 vs 구간 쿼리 (← 특정 위치에 대한 개수만을 묻는가? vs 어떤 구간의 총합을 묻는가?) 오프라인 쿼리 vs 온라인 쿼리 (← 질문을 업데이트가 모두 끝나고 하는가? vs 업데이트 도중에 질문을 하는가?) 문제는 난이도 순이 아니지만, 순서대로 읽어보시면 더 쉽게 이해하실 수 있습니다. 3, 4, 8번 문제는 세그먼트 트리에 대한 사전 지식을 필요로합니다. 세그먼트 트리에 관한 좋은 글이 이미 많기 때문에, 관련 내용은 링크로 대체하겠습니다. https://blog.naver.com/kks227/220..
