index tree 질문있습니다.

2개의 댓글이 있습니다.
  • wookayin
    wookayin

    Segment Tree 에서 구간에 update연산이 일어나는 경우는 구현이 문제마다 조금씩 다르지만(....)
    기본적으로 쿼리 구간이 어떤 노드의 구간에 완전하게 포함되면 미리 저장된 정보를 바로 쓰고 아니면 분할..의 방법이라
    [spoiler="더 보기..."]해당 구간만 update하고 그 아래 node로는 내려가지 않더라고요.
    그럼 [4 8]구간을 업데이트 하고 나중에 쿼리로 [6 10]구간을 요구하면 문제가 생기지 않을까 합니다.
    [/spoiler]
    => Query 를 할 때, 특정 구간에서 얻어낸 정보에다가, 트리에서 위로 올라오면서 "구간에 업데이트 했던 값"들을 보면서 적절히 고쳐줍니다-_-a
    말로 하는게 더 어렵군염(..) 언어 능력이 딸려서 ...


    15년 전 link
  • Kureyo
    Kureyo

    루트에서부터 쪼개서 내려오다보면 [4 8] 구간에 맞는 구간은 [6 8] 구간이 될 것이고, [4 8] 구간이 가득 찼다는 정보를 가지고 있기 때문에 [6 8]에 해당하는 길이만 반환하면 되지 않을까요? 다른 분들은 모르겠지만 저는 이렇게 구현합니다;


    15년 전 link

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