🔗 백준 2042번 - 구간 합 구하기 문제를 보자. 세그먼트 트리를 입문하면서 처음 만나게 되는 문제로 유명하다.여기서는 세그먼트 트리를 사용하지 않는, $O(M \sqrt{N})$ 풀이를 소개하려 한다.아이디어원래 세그먼트 트리에선, 구간을 반씩 쪼개어 총 $O(N\log{N})$개의 구간 합을 관리하는 아이디어를 사용한다.구간을 쪼갠다는 아이디어 자체는 같다. 여기서는 길이가 동일한 구간을 $O(\sqrt{N})$개 만들어서 각 구간의 길이 또한 $O(\sqrt{N})$이 되도록 관리한다.보통 구간 하나하나를 버킷이라 칭한다. 적용각 버킷별로 합을 저장하는 배열을 만들어 놓자.만약 위 그림처럼 특정 구간의 합을 구하려고 할 때,초록색 부분만 하나하나 직접 더해주고 파란색 부분은 미리 구해놓은 ..