구간합 구하기1 [Python] 세그먼트 트리 segment tree [세그먼트 트리] 세그먼트 트리 알고리즘 정리📌 세그먼트 트리란?세그먼트 트리는 배열의 구간 정보를 저장하여 구간 쿼리와 업데이트를 효율적으로 처리하는 자료구조입니다. 주로 구간 합, 최소값, 최대값 등을 O(log n) 시간 안에 계산할 수 있도록 도와줍니다.🚨 세그먼트 트리의 구조완전 이진 트리: 배열을 기반으로 한 완전 이진 트리 구조로 구현됩니다.노드 역할:리프 노드: 배열의 개별 원소를 저장합니다.내부 노드: 자식 노드의 값을 이용해 해당 구간의 정보를(예, 최소값 또는 합) 계산해 저장합니다.💡 주요 연산구간 쿼리: 특정 구간(예, [L, R])의 합 또는 최소/최대값을 O(log n) 시간 내에 계산할 수 있습니다.업데이트: 배열의 한 원소가 변경되었을 때, O(log n) 시간 안에 .. 2025. 3. 6. 이전 1 다음