을 의 왼쪽에서 보다 높은 가장 가까운 지점이라 하고, 없으면 으로 둔다. 다다스의 승리 조건은 다음과 같다.
이제 오른쪽 끝점 을 왼쪽부터 처리한다. 펜윅 트리에 앞선 높이들을 넣고, 를 그중 이하인 높이의 수로 둔다. 동시에 높이가 내림차순인 인덱스 스택을 유지한다. 보다 낮은 원소를 모두 뺀 개수를 이라 하면, 남은 꼭대기가 이다.
두 경우를 합친 의 기여는
이다. 이를 더한 뒤 을 펜윅 트리에 넣고 을 스택에 넣는다. 시간 복잡도는 , 공간 복잡도는 이다.
증명
이면 다다스는 보다 높은 내부 지점 중 가장 오른쪽으로 이동하여 바로 이길 수 있다. 남은 내부 높이는 모두 보다 낮으므로 따스가 움직일 수 없기 때문이다. 그런 지점이 없으면 다다스가 움직일 수 없다.
이고 , 이면 다다스는 로 이동하여 바로 이긴다. 이면 이동할 수 없다. 나머지 경우에는 다다스가 어디로 이동하든 그 위치 는 보다 왼쪽이다. 따스는 의 오른쪽에서 보다 높은 가장 왼쪽 지점으로 이동할 수 있고, 두 말 사이에는 다다스보다 높은 지점이 남지 않는다.
인 후보는 개이다. 그중 지는 경우는 이 의 오른쪽에서 처음 만난 더 높은 지점인 경우로, 방금 스택에서 빠진 개와 정확히 일치한다. 따라서 이 종류의 승리 쌍은 개이다.
인 승리 쌍은 을 만족한다. 과 사이의 높이는 모두 보다 낮으므로 이 범위의 높이는 자동으로 의 왼쪽에 있다. 따라서 이면 개를 더한다. 아직 을 넣지 않았으므로 이고, 두 식을 합치면 본문의 기여식을 얻는다.
