문제 링크

• http://icpc.me/7573

문제 링크

• http://icpc.me/2583

이전 글에서 소개했던 0-1BFS알고리즘과 함께 찾은 특정한 그래프에서 작동하는 다익스트라 알고리즘을 발견하게 되어서, 이 알고리즘도 소개를 합니다.

어제 알고리즘에 대해 검색을 하다가 코드포스 블로그에서 흥미로운 최단경로 최적화법을 찾아서, 그 방법을 소개하고자 합니다.

처리해야 할 쿼리

이전 글에서는 다음 두 가지 쿼리가 주어졌습니다.

1. 구간 [l, r]이 주어졌을 때 해당 구간의 합 구하기
2. i번째 수를 v로 바꾸기

Segment Tree란?

세그먼트 트리는 특정 구간의 합, 곱, 최대값, 최소값 등을 효율적으로 구하는 자료구조입니다.
이진 트리의 형태를 띄고 있으며 naive한 방식보다 훨씬 효율적으로 작업을 처리할 수 있습니다.

문제 링크

• https://www.acmicpc.net/problem/4008

문제 링크

• http://icpc.me/15885

문제 링크

• http://icpc.me/15885

문제 링크

• http://icpc.me/15889