구간최소값 썸네일형 리스트형 펜윅트리로 최소값구하기 펜윅트리란 어떤 배열의 특정구간 구간합과같은 쿼리가 많을경우 별도의 특별한 트리구조를 만들어 이를통해 시간복잡도문제를 해결하기 위한 자료구조입니다. 펜윅트리말고도 이와같은 트리로 세그먼트트리도 있으나 개인적으로 펜윅트리가 구현하기 깔끔하고 필요한 트리를 만들기위한 메모리를 절약할수 있으며 속도도 왠만하면 더 빠른기대값을 얻을수 있습니다. 하지만 펜윅트리로는 최소값, 최대값같은 구간값을 일반적으로 구할수가 없습니다. 구간합 같은경우 A - B 구간의 합을 구할때 1-B까지의 구간합 - 1-A까지의 구간합을 통해 계산하며 되지만 최대값 최소값같은경우 펜윅트리의 구조상 생략되는 값이 존재하기때문입니다. 펜윅트리는 어떤수를 2진수로 표현할때 1의 위치, 개수에따라 값을 구하는 방식으로 만들어지는 방식을 살펴보면.. 더보기 이전 1 다음
