인덱스 계산이 바로 주소가 된다
i번째 원소를 찾는 비용은 작지만, 범위를 벗어난 접근은 즉시 잘못된 값을 만듭니다.
배열 비용 판단 기준
배열은 인덱스 접근이 빠른 대신 중간 변경과 복사 비용이 숨어 있으므로 연산 위치를 함께 봐야 합니다.
뒤 원소 이동이 발생
삽입 위치 뒤의 원소 수만큼 이동하므로 앞쪽 변경이 많으면 비용이 커집니다.
전처리로 반복 합 축소
값 변경이 적고 합 질의가 많다면 prefix sum으로 매번 순회하는 비용을 낮춥니다.
제출 전 남길 증거
조회 중심
인덱스가 직접 주어지면 배열의 장점이 가장 크게 드러납니다.
변경 중심
앞이나 중간에 자주 넣고 빼면 이동 비용을 먼저 계산합니다.
질의 중심
같은 구간 합을 반복하면 전처리 배열을 후보에 올립니다.