OOP1 [C++] 객체지향, 제네릭 세그먼트 트리 라이브러리 구현하기 이 글에서는 재사용 가능한 제네릭 세그먼트 트리 라이브러리를 구축하는 방법에 대해 알아본다. 세그먼트 트리를 사용할 어떤 상황이 나와도 최대한 복붙만으로 문제를 해결할 수 있게 하는 것을 목표로 한다. 세그먼트 트리의 작동 원리 자체에 대해 설명하는 글은 아니기 때문에 독자가 세그먼트 트리에 대해 어느 정도 이해하고 있다고 가정한다. Motivation 세그먼트 트리는 point update & range query를 O(log N)에 처리할 때 유용하게 사용 가능한 자료구조다. 여기서 range query는 다음과 같은 것들이 주어질 수 있다: 구간 a[l..r]의 합/곱/xor을 구하기 구간 a[l..r]의 최솟값/최댓값을 구하기 구간 a[l..r]의 최대 부분연속합을 구하기 (속칭 금광세그) 구간 .. 2023. 10. 3. 이전 1 다음
