누적합

누적된 합의의미로 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것

• 앞에서부터 더함 : prefix sum
• 뒤에서부터 더함 : suffix sum

보통 코테에는 prefix sum만 나오고
suffix sum은 알고리즘 대회정도..

prefix sum

• 0번은 비워넣고 1번째부터 만들기

  • 1번째 : 1번째 = psum[1]
  • 2번째 : 1+2번째 = psum[1] + 2
  • 3번째 : 1+2+3번째 = psum[2] + 3
    ...
  • psum[i] = psum[i-1] + a[i]

• 2~5까지의 합을 구해라 : 구간 쿼리
  -> psum[5] - psum[1]

구간 쿼리가 나올 경우 :

• 정적 배열(배열의 요소가 변하지 않는 경우) : 누적합
• 동적 배열(배열의 요소가 변하는 경우) : 트리