Segment Tree

[JAVA] 백준 2042 : 구간 합 구하기

문제 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 해결방법 안녕하세요 ! 글은 쓰고 있지 않지만 꾸준히 알고리즘을 풀이하고는 있는데 최근에 세그먼트 트리를 하게 되면서 기본 구조를 알 수 있는 문제는 기록을 해두면 좋을 것 같아서 오랜만에 글을 작성해 봅니다. 세그먼트 트리는 누적합의 다음 형태라고 볼 수 있는데 누적합의 경우 구간의 합은 O(1)에 구해지지만 중간에 값이 업데이트가 될 경우 O(N)만큼 시간이 소모되기 때문에 업데이트 횟수가 많다..