algoshipda   9년 전

인덱스트리로 구간트리처럼 최대값, 최소값 쿼리를 처리하도록 구현이 가능한가요?

만약에 가능하다면 그게 어떻게 되는건지 궁금합니다.

제가 알기론 인덱스트리는 자식노드의 오른쪽 노드가 없어서 그쪽 구간에 있는 최대, 최소값은 알 수가 없을것 같거든요

만약에 된다면 단지 제일 첫 인덱스부터 어떤 인덱스 n까지 구간에 대해서만 처리할 수 있을것 같은데,

알려주시면 감사하겠습니다

amugeona   9년 전

BIT는 최대/최소 구하는 용도가 아닌걸로 알고있습니다.

algoshipda   9년 전

인덱스트리의 정확한 정의가 뭐죠? 그냥 완전이진트리를 배열로 구현하고 인덱스연산으로 방문하는게 인덱스트리인가요? 그러면 BIT랑은 다른 개념이라고 봐야할까요?

amugeona   9년 전

BIT는 누적되는 정보를 이용해 구간 정보를 구할때 쓰시면 됩니다.

IT는 BIT + 최대 / 최소 등 구간을 대표하는 정보를 구할 때 쓰시면 됩니다.

IT가 BIT에 비해 평균 연산량과 메모리를 더잡아먹습니다.

algoshipda   9년 전

감사합니다 도움이 됐습니다.

댓글을 작성하려면 로그인해야 합니다.