수업 목표 및 핵심 역량

- 정적 데이터와 동적 데이터의 구간 질의 복잡도를 정량적으로 분석합니다. - 점 갱신와 구간 합 갱신 시의 적절한 자료구조 특징을 규명합니다. - 펜윅 트리의 LSB 연산 i & (-i)의 수학적 의의를 파악합니다. - 레이지 전파를 통한 구간 일괄 갱신의 최적화 흐름을 내재화합니다.

누적 합 (Prefix Sum)

- 누적합 관계식을 구성하여 뺄셈 한 번으로 구간 합 산출

# 8049번: 구간 합 쿼리 발췌
prefix = [0] * (n + 1)
for i in range(1, n + 1):
    prefix[i] = prefix[i - 1] + arr[i - 1]

# query(l, r)
ans = prefix[r] - prefix[l - 1]

스파스 테이블 (Sparse Table)

- 2의 거듭제곱 크기 구간의 최솟값을 빌드하여 임의의 구간 RMQ를 $O(1)$에 포괄

# 8050번: 구간 최솟값 쿼리 발췌
for k in range(1, log_n):
    for i in range(n - (1 << k) + 1):
        sparse[k][i] = min(sparse[k - 1][i], sparse[k - 1][i + (1 << (k - 1))])

# query(l, r)
k = int(math.log2(r - l + 1))
ans = min(sparse[k][l], sparse[k][r - (1 << k) + 1])

펜윅 트리 (Fenwick Tree / BIT)

- 점 갱신과 구간 합을 비트 연산 기반 트리 구조로 대칭 갱신

# 8051번: 구간 합 업데이트 발췌
def update(i, diff):
    while i <= n:
        bit[i] += diff
        i += i & (-i)

def query(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & (-i)
    return s

오류 예방 및 안정성 체크

- **0번 인덱스 접근 차단**: 펜윅 트리는 LSB 비트 시프트 특징으로 인해 인덱스 0 진입 시 무한 루프에 걸림 - **구간 업데이트 범위 유의**: 듀얼 BIT 기반 갱신 시 경계 범위 r + 1 처리가 배열 경계를 넘지 않도록 크기 보정 확인 - **결합 법칙 준수**: 스파스 테이블은 중복 계산이 무관한 연산(min, max, gcd)에만 유효함을 숙지