누적합 개념 정리누적합: 배열에서 앞에서부터 해당 인덱스까지의 원소의 값을 모두 더한 것구간합: i부터 j까지 해당 구간 사이 원소의 합예를 들어 5 4 3 2 1 이라는 값을 가진 5 크기의 배열 arr가 있다고 하자. 1. 첫번째 누적합은 기존의 값이 그대로 내려온다.2. 누적합과 그 다음 값을 더한 값이 두번째 누적합이 된다. 3. 위 과정을 반복해서 누적합 배열을 만든다.만약 1~ 3번째 구간의 합을 구하고 싶다면 5+4+3=12 이므로 즉 인덱스 2번의 누적합 값이다. 2~4번째 구간의 합을 구하고 싶다면 4+3+2=9인데, 이 값은 1~4번째까지 더한 값 14에서 첫번째 값 5를 빼면 구할 수 있다. 정리하자면 i부터 j까지의 구간합은 j번째 누적합 - (i-1)번째 누적합이다. 누적합을 쓰..
