쿼리(연산)를 누적하여 마지막 한 번에 연산하기(feat. 누적합)

https://hsdevelopment.tistory.com/772

 

 

 

 

배열이 주어지고, 배열의 구간에 수를 더하고 빼는 쿼리가 있다.

세그먼트 트리를 이용해도 되지만, 우리는 연산 중간에 배열의 값을 알 필요가 없고,

 

모든 쿼리(연산) 이후에 마지막 단 한 번만 구하면 되기 때문에,

 

누적합을 이용할 수 있다.