#누적 합 1

누적 합 (Prefix Sum) 정리

누적 합 배열의 앞에서부터의 합을 미리 구해 두어, 임의 구간의 합을 O(1) 에 답하는 기법. 매번 구간을 직접 더하면 질의 1번에 O(N) , 질의가 많으면 O(NQ) 로 터진다. 누적 합을 한 번 O(N) 에 만들어 두면 그 뒤