일단 원래 질문부터 답을 드리자면
구간노드 (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) 이 되니까요
smu201111192 7년 전
직선에서의 점들간의 거리를 세그트리로 저장해야될 일이 생겼는데 . 중간에 비는 부분은 어떻게 처리해주나요? 예를들어 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