Line Sweeping2

nlogn 알고리즘

lv = 왼쪽 값, rv = 오른쪽 값

if lv == 0이면: 오른쪽 자식의 rv 왼쪽 자식의 rv를 더한값을 자신의 rv로 삼는다.

if lv > 0 이면: 자식노드의 개수만큼을 rv로 삼는다.(즉 2,4,8---)

시작 점 = 사각형의 왼쪽 아래 좌표

끝 점 = 사격형의 오른쪽 위 좌표

if시작 점일 경우: 포함된 자식노드만을 모두 포함 할 수 있는 부모노드까지만 본다.

                         자식노드가 있을경우 rv = 자식노드의 수

                                                        lv = lv + 1

                         자식노드가 없을경우 rv = rv + 1

                                                        lv = lv + 1

if끝 점일 경우: 포함된 자식노드만을 모두 포함 할 수 있는 부모노드까지

                          lv = lv -1

                          lv > 0 이면 rv = 자식노드의 수

                          lv == 0 이면 rv = 자식노의 rv값을 더한 값

이렇게 시작 점 에서 연산이 끝나면 위로 올라가서 위과정을 최초 Root까지 반복한다.

각 과정에서의 Root의 rv * (next x - current x)을 다 더하면 넓이가 나온다!

예) 노란색 원 시작점!