누적합

만약 a에서 b구간의 합을 알고 싶을때 물론

a에서 b까지의 구간을 직접 하나하나 움직여가면서 더하는 법도 있다.

하지만, 그러한 케이스를 여러개 계산할때는

a에서 b까지 계속 움직이다 보면 케이스마다 실행수가 엄청 쌓이고, 

결국 효율성에서 최악이다.

 

따라서, 그러할 경우엔 누적합을 쓰는 것이다.

누적합이란,

예를들어 int 배열 1 2 3 4 5방이 있다. 이때 3에서 5번방까지의 합을 구하고, 2번방에서 4번방의 합을 구하고 싶다.

만약 하나하나 더한다면, 3,4,5   2,3,4 총 6번의 실행을 해야한다. 

하지만 만약 처음에 1은 1, 2는 1+2의 값, 3은 1+2+3의 값....한다면

3에서 5번방은 5번방빼기 2번방, 2번방에서 4번방은 4번방 빼기 1번방을 하면 원하는 값을 구할 것이다.

총 횟수는 1,2,3,4,5로 물론 여기선 1의 차이밖에 없지만,

이 방의 수가 확 커진다면, 그 차이는 확연하게 드러날 것이다.