Q : N개의 정수 배열에서 a~b까지 합을 구하려면 어떻게 하나요? A : for문을 돌면서 더해요! $O(N)$ Q : 그럼 Q개의 쿼리형식으로 들어온다면요? A : 누적합배열을 사용해요! $O(N+Q)$ Q : 그럼 여기에 업데이트도 있다면 있다면 어떻게 할까요? A : 세그먼트 트리를 쓰면 되죠! $O(Q \log N)$ 위의 모든 답변은 실제로 정답이고 더 어려운 알고리즘이 하위 문제를 해결할 수 있다. 예를들어 누적합으로 1번 문제를 해결할 수 있고 세그먼트 트리로 1, 2번 문제를 해결할 수 있다. 하지만 위 문제들을 제곱근 분할법(a.k.a. 루트질)을 사용해서 해결할 수도 있다! 물론 쉬운 알고리즘을 사용할 수 있다면 그걸 사용하는게 좋겠지만 연습용으로 풀기 좋다. 어떻게 해결할 지 알아..
