인덱스트리로 구간트리처럼 최대값, 최소값 쿼리를 처리하도록 구현이 가능한가요?
만약에 가능하다면 그게 어떻게 되는건지 궁금합니다.
제가 알기론 인덱스트리는 자식노드의 오른쪽 노드가 없어서 그쪽 구간에 있는 최대, 최소값은 알 수가 없을것 같거든요
만약에 된다면 단지 제일 첫 인덱스부터 어떤 인덱스 n까지 구간에 대해서만 처리할 수 있을것 같은데,
알려주시면 감사하겠습니다
BIT는 최대/최소 구하는 용도가 아닌걸로 알고있습니다.
인덱스트리의 정확한 정의가 뭐죠? 그냥 완전이진트리를 배열로 구현하고 인덱스연산으로 방문하는게 인덱스트리인가요? 그러면 BIT랑은 다른 개념이라고 봐야할까요?
BIT는 누적되는 정보를 이용해 구간 정보를 구할때 쓰시면 됩니다.
IT는 BIT + 최대 / 최소 등 구간을 대표하는 정보를 구할 때 쓰시면 됩니다.
IT가 BIT에 비해 평균 연산량과 메모리를 더잡아먹습니다.
감사합니다 도움이 됐습니다.
댓글을 작성하려면 로그인해야 합니다.
algoshipda 9년 전
인덱스트리로 구간트리처럼 최대값, 최소값 쿼리를 처리하도록 구현이 가능한가요?
만약에 가능하다면 그게 어떻게 되는건지 궁금합니다.
제가 알기론 인덱스트리는 자식노드의 오른쪽 노드가 없어서 그쪽 구간에 있는 최대, 최소값은 알 수가 없을것 같거든요
만약에 된다면 단지 제일 첫 인덱스부터 어떤 인덱스 n까지 구간에 대해서만 처리할 수 있을것 같은데,
알려주시면 감사하겠습니다