삽입정렬 시간재기에서 구간트리

  • chochogogo
    chochogogo

    삽입정렬 시간재기를 구간트리 이용해서 풀기관련 질문있습니다.

    예를들어, 임의의 배열 내 임의구간에서의 최소 값 구하기를 구간트리를 이용해서 풀면, 구간트리 내 각 원소의 의미는 해당 섹터 에서의 최소값
    을 의미합니다.

    그렇다면 해당 문제를 구간트리를 이용해서 풀때 해당 구간트리 내 각 원소는 무엇을 의미하게 되나요???


    8년 전
2개의 댓글이 있습니다.
  • WeissBlume
    WeissBlume

    그걸 알면 문제가 너무 쉬워져요 :$

    수가 1..n이라고 하고, tree[i]가 i란 수가 지금까지 등장한 횟수라고 합시다. 이렇게 되면 수를 한 개씩 순회하면서 inversion(자신보다 먼저 등장했지만 자신보다 큰 수의 개수)을 셀 수 있겠죠.


    8년 전 link
  • chochogogo
    chochogogo

    아.... 이제야 확인했내요.. 답변 감사드립니다~!


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