Segment Tree를 활용한 구간 내 최대 부분합을 찾는 문제는 주로 다음과 같은 조건의 쿼리가 주어진다.
- 수열에서 a번째 숫자를 b로 바꾸는 쿼리
- l, r (l<=r)이 주어졌을 때, 수열의 [l,r]내에서 연속된 부분합의 최댓값을 구하는 쿼리
노드에 단순히 최대 부분합만 담고 있다고 가정해보자.
자식 노드 둘을 합칠 때, 둘 중 최댓값을 고르게 되면 왼쪽 절반 안에 속해있는 부분합과 오른쪽 절반안에 속해있는 부분합 밖에 알 수 없다. 즉, 두 구간을 걸친 부분들의 합은 고려해 줄 수 없다. 따라서 아래와 같은 방식을 채택해야 한다.
세그먼트 트리의 각 노드에 들어갈 변수는 다음과 같다.
tree[i] = {
lSum = 왼쪽 절반 최댓값, max(l.lSum, l.sum + r.lSum)
rSum = 오른쪽 절반 최댓값, max(r.rSum, r.sum + l.rSum)
maxSum = 구간 최댓값, max(lSum, rSum)
sum = 구간 총 합, (lSum+rSum)
};
tree[i] = x의 구간 i에 대해 {총합, 왼쪽절반 최대값, 오른쪽절반 최대값, 최대값}을 담아서 새로운 (x,cost)를 모두 업데이트한 후 정답을 갱신해주면 된다.
Code update coming soon ...
BE Developer