책 15단원의 15.15 코드 unionArea 함수에서 질문 있습니다

  • infoefficiency
    infoefficiency

    평면 스위핑에서

    배열 대신 펜윅 트리를 쓰면

    시간 복잡도를 줄일 수 있다고 하였는데

    정확히 어떻게 써야 되는지 감이 잘 오지 않습니다.

    자세한 설명 해주시면 정말정말 감사하겠습니다 ㅠㅠ


    9년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    음.. 지금 곰곰히 생각을 해 보니, 왜 펜윅 트리를 써서 줄일 수 있다고 했는지 모르겠군요. 이 경우는 구간 트리를 사용하면 됩니다. 제가 옛날에 구현해 둔 코드가 여기 있는데 참조해 보세요. 평면 스위핑에서 [y1, y2] 범위에 1을 더한다 - 뺀다 연산을 change() 함수를 사용해 O(\lg n) 시간에 할 수 있지요.


    9년 전 link
  • infoefficiency
    infoefficiency

    change를 기존 코드에 어떻게 써야할지 감이 잘 안오네요 ㅠㅠ 조금만 더 설명 해주실 수 있을까요?


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.