Tags

2 pages

Kadane

[Algorithm] cpp-python 백준 16993번: 연속합과 쿼리 (세그먼트 트리)

길이 N(≤100,000) 수열에 대해 구간 [i,j]의 최대 연속합을 O(log N)으로 질의하는 세그먼트 트리 풀이입니다. 각 노드에 합·최대 접두/접미합·구간 최대합을 저장하고 병합 규칙으로 정답을 계산합니다. 음수 전용 구간·단일 원소·전부 음수인 경우를 안전하게 처리하며, 시간·공간 복잡도와 실수 포인트를 정리했습니다.
[Algorithm] cpp-python 백준 16993번: 연속합과 쿼리 (세그먼트 트리)