✓

태그:

37. 세그먼트 트리 CLASS 3

합을 상수 시간에 구해야한다고요? 합을 미리 구해놓는건 어떤가요?

풀이 비스무리한거 보기

주어진 수열의 범위를 정해주었을 때 해당 범위의 합을 구하는 문제입니다. M의 범위가 100000 이하인 것으로 보아 상수 시간 내에 각 쿼리에 대한 답안을 내야할 것으로 보입니다. 이 때 사용할 수 있는 것으로 누적 합이 있습니다. 처음부터 해당 위치까지의 누적 합을 저장해놓고 처음부터 j까지의 범위의 합에서 처음부터 i-1까지의 범위의 합을 빼면 i부터 j까지의 부분합을 구할 수 있습니다. 수식으로 표현하면 아래와 같이 됩니다.

\[\sum_{k=1}^{j}a_k-\sum_{k=1}^{i-1}a_k=\sum_{k=i}^{j}a_k\]

누적 합이 위의 각 항에 해당하는 부분합을 저장하는 것이기 때문에 상수 시간에 우변에 해당하는 합을 구할 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-04-04 22:17:45

---