직선에서의 점들간의 거리를 세그트리로 저장해야될 일이 생겼는데 . 중간에 비는 부분은 어떻게 처리해주나요? 예를들어 1번점에서 ~7번점까지들간의 거리를 세그트리에 모두 저장하면 세그틀에는 1~7거리 저장된 노드 1~4, 5~8, 1~2,  3~4 , 5~6 , 7~8  , 1~1 , 2~2 , 3~3  ,4~4 , 5~5 , 6~6 ,7~7 ,8~8 이렇게 저장이 되어있을텐데 3~7사이의 거리를 알고싶어서 쿼리를 3~7쿼리를 호출하면 3~4+ 5~6 +7~7거리를 불러오게되서4~5, 6~7 거리가 비는데 어떻게 처리를 해줘야될까요?

풀고있는  문제는 요녀석입니다. http://codeforces.com/problemset/problem/610/D



ntopia   3달 전

일단 원래 질문부터 답을 드리자면

구간노드 (i , j) 에는

점 i-1 부터 점 j 까지의 거리를 저장

하면 편하게 구현할 수 있습니다

예를 들어 노드 (2 , 2) 에는 점1부터 점2까지의 거리

노드 (3, 4) 에는 점2부터 점4까지의 거리가 저장되죠

그렇게 해놓고 내가 실제로 점 a 와 점 b 사이의 거리가 궁금하다 그러면

구간 쿼리를 a+1, b  로 날리면 되겠죠

그럼 사이사이가 비지 않고 꽉찬 값을 잘 가져오게 됩니다

이를 위해 가상의 점 0번 점도 추가하면 구현하기 편하겠죠...



근데 이건 그냥 누적합만 갖고 있어도 구할 수 있을 것 같은데요..

s(i) = 점1부터 점i까지의 거리   라고 하면

점i부터 점j까지의 거리는 s(j) - s(i-1) 이 되니까요

감사합니다.

알려주신 두 방법으로  접근해서 다시 풀어보겠습니다.!

댓글을 작성하려면 로그인해야 합니다.