작성한 질문수 19

1

안녕하세요 Kyoung님 ㅎㅎ

음.. 제가 설명이 좀 부족했던 것 같네요.. ㅠ

좀 더 설명을 드리자면요 다음과 같습니다. :)

그림상 파란 화살표 표시한 것이 3,4,6 인덱스를 의미 하는 것인지 그리고, 3,4,6째 인덱스를 비교한다는 것이 왜 필요한 것인지 궁금합니다.

>> A의 요소 2, 4, ... , 8까지의 요소중 최소값을 구해야 합니다.

여기서 0 ~ 6까지의 요소를 다 탐색하는 것이 아니라 펜윅트리를 만들게 되면

min[0, 3] = 3

min[4, 5] = 4

min[6] = 6

부분의 최솟값만 보면 된다는 의미입니다.

파랑 노드를 만들면 된다고 갑자기 설명을 하시는데, (강의 3:03 구간)
그림상 주황색 노드(3,4,10,11)의 의미, 파랑색 노드(1,2,3,4)의 의미에 대한 안내도 없고

>> 주황색노드는 그냥 하나의 배열입니다. 3, 4, 10, 11이라는 배열입니다.

파란색노드는 해당 펜윅트리의 노드를 만든다는 의미입니다.

앞의 그림 처럼 3의 요소가 1, 2, 4 노드에 반영되는 것을 볼 수 있습니다.

4라는 요소는 2, 4에 반영되고 있는 것을 볼 수 있습니다.

펜윅트리의 코드를 보시면 다음과 같습니다.

void update(vector<long long> &tree, int i, long long diff) {
    while (i < tree.size()) {
        tree[i] += diff;
        i += (i & -i);
    }
}

앞의 코드에서 만약 요소 3 즉, 1번째요소(펜윅트리를 만들 때는 0번째가 아니라 1번째요소 부터 만들어서 진행합니다.)

를 기반으로 펜윅트리를 만든다면 다음과 같은 과정을 거쳐서 트리가 만들어집니다.

tree[1] += 3

i += 1

tree[2] += 3

i += 2

tree[4] += 3

i += 4

종료.

즉, 이런식으로 1, 2, 4라는 인덱스를 가진 tree의 노드에 해당 값이 반영되는 것을 의미합니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.