fin   3년 전

자기 왼쪽 자식과 오른쪽 자식의 누적합의 값을 보고 왼쪽, 오른쪽 자식 중 어디에 타겟이 있는지를 찾아야하는데

지금 내가 찾는 타겟이 만약 왼쪽자식보다 커서 오른쪽 자식으로 가야한다면 왼쪽 자식의 누적합을 빼줘야합니다.

예시를 들면 지금 내가 찾는 타겟이 10등이고 왼쪽 자식의 누적합의 값이 8이고 오른쪽 자식의 누적합의 값이 12라면

내가 찾는 등수는 오른쪽 서브트리에서 2등인 값입니다.

그렇기 때문에 오른쪽 서브트리로 이동하면서 왼쪽 서브트리의 값 8을 빼주고 이동합니다.


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