트리 기반 구간 연산 최적화 기법
트리 구조를 활용한 구간 갱신과 합계 계산은 알고리즘에서 핵심적인 기술입니다. 기본적으로 차분 배열을 사용해 구간 갱신을 단일 원소 갱신으로 변환하고, 두 개의 트리 구조를 유지해 효율적으로 계산합니다.
구간 합계 계산 공식:
$$\sum_{i=1}^{x}\sum_{j=1}^{i}c_j = (x+1)\sum_{i=1}^{x}c_i - \sum_{i=1}^{x}(i \cdot c_i)$$
따라서 $\sum c_i$와 $\sum (i \cdot c ...
10월 5일 00:35에 게시됨