배열 메모리 모델

배열 인덱스 범위 고정

0부터 n-1까지인지, 1-based로 둘지 처음에 정하고 변환 지점을 줄인다.

2차원 배열은 메모리 배치와 같은 방향으로 순회하면 캐시 효율이 좋아진다.

vector push_back은 평균적으로 빠르지만 재할당 시 참조와 iterator가 무효화될 수 있다.

Access

O(1) 위치 접근 인덱스만 알면 바로 원소 위치를 계산한다.

배열 인덱스 범위 검사는 별도다.

Insert

중간 삽입 O(n) 뒤 원소를 밀어야 하므로 빈번하면 다른 구조를 본다.

끝 삽입과 구분한다.

Cache

연속 순회 이점 인접 원소 접근이 CPU cache에 잘 맞는다.

linked list보다 빠른 경우가 많다.

Prefix

누적 배열 구간 합을 빠르게 답하려면 원본 배열 위에 보조 배열을 만든다.

초기 0칸을 두면 경계가 단순하다.

배열 인덱스 범위 i < n과 i <= n이 섞이지 않는가.

무효화 vector 재할당 뒤 저장해 둔 포인터나 참조를 다시 쓰지 않는가.

구간 구간 질의가 많다면 매번 합산하지 않고 prefix 구조를 쓰는가.

prefix[0] = 0;
for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + a[i];
// sum[l, r) = prefix[r] - prefix[l]