금광세그1 [PS를 위한 자료구조 7강] 세그먼트 트리의 응용 (금광 세그) PS를 위한 자료구조 1-7강 # 다양한 세그먼트 트리 테크닉, 금광 세그 # 에 대해 알아보겠습니다. 아래의 문제를 한 번 보겠습니다. [연속합과 쿼리] https://www.acmicpc.net/problem/16993 구간 합 구하기 4를 풀어보신 분들이라면 다음과 같은 생각을 할 수 있을 것 같습니다. 배열을 누적합으로 만든 다음, 구간 내 최댓값에서 최솟값을 빼면 되지 않을까요? 아쉽게도 해결하기 어려운 반례가 존재합니다. 최댓값이 최솟값보다 앞서서 나오는 경우에는 해결이 불가능하기 때문이죠. 위의 문제를 해결하기 위해 만들어진 테크닉이 바로 "금광 세그"라고 불리는 테크닉입니다. 금광이 나오는게 좀 뜬금없는데, 금광은 2014년 중등부 정보올림피아드에서 출제된 문제의 .. 2022. 3. 24. 이전 1 다음
