P5 2243 사탕상자

20분 11초
맛 번호의 개수를 가지고 있는 세그먼트 트리를 이용하여 해결한다. 즉, tree[1]:= 맛 1 ~ 1,000,000의 모든 개수 가 된다.
x 번째로 맛있는 사탕을 찾고 싶으면 tree[2*node]의 값 보다 작으면 왼쪽 child로, 그렇지 않다면 오른쪽 child에 있다는 뜻이다.

P4 10999 구간 합 구하기 2

1시간 6분 42초
'느리게 갱신되는 세그먼트'를 사용하여 풀었어야 했다. 구간 변경이 존재하기 때문에 일반적인 세그먼트 트리로는 시간초과가 난다. 느리게 갱신되는 세그먼트를 알지 못해서 풀지 못했다.

'느리게 갱신되는 세그먼트 트리' 란?

한 노드에 value와 lazy라는 변수를 저장한다.
구간합이나 구간변경을 할 때 대표노드(범위가 완전히 충족되는 노드)가 존재하는데
이때 대표노드의 자식노드들의 값을 바로 업데이트시키는 것이 아니라
대표노드의 lazy값에 넣어서 후에 필요할 때마다 업데이트해 주는 방식이다.