문제 링크 : https://www.acmicpc.net/problem/13557 문제 태그 더보기 Segment Tree 문제 소개 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. x1 y1 x2 y2: x1 ≤ i ≤ y1, x2 ≤ j ≤ y2, i ≤ j인 모든 (i, j)에 대해서 Ai + ... + Aj의 최댓값을 출력한다. (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ N, x1 ≤ y1, x2 ≤ y2) 문제 풀이 주어진 구간 내에서 최대 부분합을 구하는 문제는 Segment Tree를 이용해서 풀 수 있음이 잘 알려져 있다. 특히 "금광 세그"라고 불리는 테크닉이다. 이 부분에 대해서는 이 글 을 참조하자. 관찰 1..